记录详情

Time Exceeded


  
# 状态 耗时 内存占用
#1 Accepted 2ms 376.0 KiB
#2 Accepted 2ms 340.0 KiB
#3 Accepted 2ms 340.0 KiB
#4 Accepted 2ms 340.0 KiB
#5 Accepted 2ms 456.0 KiB
#6 Accepted 6ms 504.0 KiB
#7 Accepted 6ms 536.0 KiB
#8 Accepted 4ms 376.0 KiB
#9 Accepted 6ms 524.0 KiB
#10 Accepted 12ms 572.0 KiB
#11 Accepted 8ms 732.0 KiB
#12 Accepted 109ms 1.254 MiB
#13 Accepted 68ms 1.242 MiB
#14 Accepted 102ms 1.445 MiB
#15 Accepted 139ms 1.688 MiB
#16 Accepted 2005ms 14.723 MiB
#17 Accepted 3292ms 16.023 MiB
#18 Accepted 1372ms 9.828 MiB
#19 Accepted 1621ms 10.555 MiB
#20 Time Exceeded ≥5005ms ≥24.332 MiB

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn=1e6+10,size=2000;
int a[maxn],now[maxn],ans=1,out[maxn];
struct node{
    int l,r;
    int index;
}query[maxn];
int cmp(node x,node y)
{
    if((int)x.l/size == (int)y.l/size) return x.r<y.r;
    return x.l<y.l; 
}
void upd(int x){if(++now[a[x]]==1) ans++;}
void del(int x){if(--now[a[x]]==0) ans--;}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    string s;cin>>s;
    for(int i=0;i<n;i++) 
    {
        if(s[i]=='+')a[i+1]=a[i]+1;
        if(s[i]=='-')a[i+1]=a[i]-1;
        if(s[i]=='*')a[i+1]=a[i]+3;
    }
    for(int i=1;i<=m;i++) scanf("%d%d",&query[i].l,&query[i].r),query[i].index=i;
    sort(query+1,query+1+m,cmp);
    int nowl=1,nowr=1;now[a[1]]++;
    for(int i=1;i<=m;i++)
    {
        while(query[i].r>nowr) nowr++,upd(nowr);
        while(query[i].r<nowr) del(nowr),nowr--;
        while(query[i].l<nowl) nowl--,upd(nowl);
        while(query[i].l>nowl) del(nowl),nowl++;
        out[query[i].index]=ans;
    }
    for(int i=1;i<=m;i++) printf("%d\n",out[i]);
    return 0;
}

信息

递交者
类型
递交
题目
P1012 F 奇怪的程序(Hard) /[模板]莫队算法
语言
C++
递交时间
2021-12-30 16:08:48
评测时间
2021-12-30 16:08:48
评测机
分数
95
总耗时
≥13772ms
峰值内存
≥24.332 MiB