oj.uz

Submission #979037

# Submission time Handle Problem Language Result Execution time Memory
979037 2024-05-10T06:49:40 Z Kenjikrab Street Lamps (APIO19_street_lamps) C++14
20 / 100
 5000 ms 23088 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;
char s[n_max];
arr4 arr[3*n_max];
int ans[n_max];
int cnt=0;
int fen[n_max];
void upd(int idx,int val)
{
    for(;idx<n_max;idx+=idx&-idx)fen[idx]+=val;
}
int qr(int idx)
{
    int ret=0;
    for(idx;idx;idx-=idx&-idx)ret+=fen[idx];
    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])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);
    memset(ans,-1,sizeof(ans));
    int n,q;
    scanf("%d%d%s",&n,&q,s+1);
    zero.insert(0);
    for(int i=1;i<=n;i++)
    { 
        s[i]-='0';
        if(s[i]==0)zero.insert(i);
    }
    zero.insert(n+1);
    char com[10];
    for(int i=1;i<=q;i++)
    {
        scanf("%s",com);
        if(com[0]=='q')
        {
            int a,b;
            scanf("%d%d",&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;
            scanf("%d",&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;
        }
    }
    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 printf("%d\n",ans[i]);
    }
    return 0;
}

Compilation message

street_lamps.cpp: In function 'int qr(int)':
street_lamps.cpp:22:9: warning: statement has no effect [-Wunused-value]
   22 |     for(idx;idx;idx-=idx&-idx)ret+=fen[idx];
      |         ^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d%d%s",&n,&q,s+1);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%s",com);
      |         ~~~~~^~~~~~~~~~
street_lamps.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |             scanf("%d%d",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:73:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |             scanf("%d",&a);
      |             ~~~~~^~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 23088 KB Output is correct
2 Correct 654 ms 22308 KB Output is correct
3 Execution timed out 5060 ms 10812 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 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 3 ms 6604 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Execution timed out 5095 ms 20592 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6488 KB Output is correct
2 Correct 5 ms 6488 KB Output is correct
3 Correct 5 ms 6492 KB Output is correct
4 Correct 4 ms 6644 KB Output is correct
5 Execution timed out 5078 ms 13660 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 493 ms 23088 KB Output is correct
9 Correct 654 ms 22308 KB Output is correct
10 Execution timed out 5060 ms 10812 KB Time limit exceeded
11 Halted 0 ms 0 KB -