oj.uz

Submission #979027

# Submission time Handle Problem Language Result Execution time Memory
979027 2024-05-10T06:34:25 Z Kenjikrab Street Lamps (APIO19_street_lamps) C++14
20 / 100
 5000 ms 29576 KB 
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
int const n_max=3e5+10;

typedef array<int,4> arr4;
set<int> zero;
arr4 arr[4*n_max];
vector<int> ans(4*n_max,-1);
int cnt=0;
int fen[4*n_max];
void upd(int idx,int val)
{
    for(int i=idx;i<4*n_max;i+=i&-i)fen[i]+=val;
}
int qr(int idx)
{
    int ret=0;
    for(int i=idx;i>0;i-=i&-i)ret+=fen[i];
    return ret;
}
void sol(int l,int r)
{
    if(l>=r)return;
    int mid=(l+r)>>1;
    sol(l,mid);sol(mid+1,r);
    
    
    int p=l;
    for(int i=mid+1;i<=r;i++)
    {
        if(arr[i][2]!=0)continue;
        while(p<=mid&&arr[p][1]>=arr[i][1]){upd(arr[p][3],arr[p][2]);p++;}
        ans[arr[i][3]]+=qr(arr[i][3]);
    }
    for(int i=l;i<p;i++)
    {
        upd(arr[i][3],-arr[i][2]);
    }
    inplace_merge(arr+l,arr+mid+1,arr+r+1,[&](const arr4 &a,const arr4 &b)
    {return a[1]>b[1];});
}
signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    zero.insert(0);
    s=" "+s;
    for(int i=1;i<=n;i++)
    { 
        s[i]-='0';
        if(s[i]==0)zero.insert(i);
    }
    zero.insert(n+1);
    for(int i=1;i<=q;i++)
    {
        string com;
        cin>>com;
        if(com[0]=='q')
        {
            int a,b;
            cin>>a>>b;
            b--;
            arr[cnt++]={a,b,0,i};
            if(*lower_bound(zero.begin(),zero.end(),a)<=b)ans[i]=0;
            else ans[i]=i;
        }
        else
        {
            int a;
            cin>>a;
            if(s[a])
            {
                auto it=upper_bound(zero.begin(),zero.end(),a);
                int l=*prev(it),m=a,r=*it;
                arr[cnt++]={l+1,r-1,i,i};
                arr[cnt++]={l+1,m-1,-i,i};
                arr[cnt++]={m+1,r-1,-i,i};
                zero.insert(a);
            }
            else
            {
                auto it=find(zero.begin(),zero.end(),a);
                int l=*prev(it),m=a,r=*next(it);
                arr[cnt++]={l+1,r-1,-i,i};
                arr[cnt++]={l+1,m-1,i,i};
                arr[cnt++]={m+1,r-1,i,i};
                zero.erase(it);
            }
            s[a]^=1;
        }
    }
    cout<<endl;
    sort(arr, arr+cnt, [&](const arr4 &a, const arr4 &b)
    {return a[0]^b[0] ? a[0]<b[0] : ((a[1]!=b[1])? a[1]>b[1]:(b[2]==0)); });
    sol(0,cnt-1);
    for(int i=1;i<=q;i++)
    {
        if(ans[i]==-1)continue;
        else cout<<ans[i]<<"\n";
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Output is correct
2 Correct 2 ms 11356 KB Output is correct
3 Correct 2 ms 11356 KB Output is correct
4 Correct 2 ms 11356 KB Output is correct
5 Correct 2 ms 11364 KB Output is correct
6 Correct 2 ms 11356 KB Output is correct
7 Correct 2 ms 11256 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 507 ms 29576 KB Output is correct
2 Correct 661 ms 29476 KB Output is correct
3 Execution timed out 5042 ms 12928 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11356 KB Output is correct
2 Correct 4 ms 11380 KB Output is correct
3 Correct 6 ms 11352 KB Output is correct
4 Correct 3 ms 11608 KB Output is correct
5 Execution timed out 5068 ms 21700 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11352 KB Output is correct
2 Correct 6 ms 11356 KB Output is correct
3 Correct 9 ms 11356 KB Output is correct
4 Correct 6 ms 11336 KB Output is correct
5 Execution timed out 5064 ms 15048 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11356 KB Output is correct
2 Correct 2 ms 11356 KB Output is correct
3 Correct 2 ms 11356 KB Output is correct
4 Correct 2 ms 11356 KB Output is correct
5 Correct 2 ms 11364 KB Output is correct
6 Correct 2 ms 11356 KB Output is correct
7 Correct 2 ms 11256 KB Output is correct
8 Correct 507 ms 29576 KB Output is correct
9 Correct 661 ms 29476 KB Output is correct
10 Execution timed out 5042 ms 12928 KB Time limit exceeded
11 Halted 0 ms 0 KB -