oj.uz

Submission #931956

# Submission time Handle Problem Language Result Execution time Memory
931956 2024-02-22T16:04:55 Z sleepntsheep Street Lamps (APIO19_street_lamps) C++17
20 / 100
 5000 ms 14152 KB 
#include<stdio.h>
#include<stdlib.h>
#define N 300005

void f_u(int*t,int p,int k){ for(;p<N;p+=p&-p)t[p]+=k; }
int f_q(int*t,int p){int z=0;for(;p;p-=p&-p)z+=t[p];return z;}
int f_lb(int*t,int k){if(!k)return 0;int p=0,z=0;for(int j=1<<19;j>>=1;)if(p+j<N&&z+t[p+j]<k)z+=t[p+=j];return p+1;}

int f[2][N],p[1<<20][3],pn,q[1<<20][4],qn,n,Q;char s[N],op[7];
void A(int a,int b,int t){if(a<1)a=1;if(b>n)b=n;p[pn][0]=a,p[pn][1]=b,p[pn++][2]=t;}
int main(){scanf("%d%d%s",&n,&Q,s+1);
for(int r=1;r<=n;++r)if(s[r]=='1'){int l=r;while(s[r]=='1')++r;A(l,r-1,0);}
for(int i=1;i<=n;++i)f_u(f[s[i]&1],i,1);
for(int i=1,a,b;i<=Q;++i){scanf("%s%d",op,&a);
    if(*op=='q'){scanf("%d",&b);q[qn][0]=a,q[qn][1]=--b,q[qn][2]=i;++qn;}
    else{
        if(s[a]=='1')
        {
            int x=f_q(*f,a),l=f_lb(*f,x),r=f_lb(*f,x+1);
            A(l+1,r-1,-i);if(l+1<=a-1)A(l+1,a-1,i);if(a+1<=r-1)A(a+1,r-1,i);
        }
        else
        {
            int x=f_q(f[1],a),l=f_lb(f[1],x),r=f_lb(f[1],x+1);
            if(l==a-1&&a+1==r){ int X=f_q(*f,a),ll=f_lb(*f,X-1),rr=f_lb(*f,X+1);A(ll+1,a-1,-i);A(a+1,rr-1,-i);A(ll+1,rr-1,i); }
            else if(l==a-1) { int X=f_q(*f,a),ll=f_lb(*f,X-1); A(ll+1,a-1,-i);A(ll+1,a,i); }
            else if(a+1==r) { int X=f_q(*f,a),rr=f_lb(*f,X+1); A(a+1,rr-1,-i),A(a,rr-1,i); }
            else A(a,a,i);
        }
        f_u(f[s[a]&1],a,-1);s[a]^=1;f_u(f[s[a]&1],a,1);
    }
}

for(int i=0;0&&i<pn;++i)printf(" : %d %d %d\n",p[i][0],p[i][1],p[i][2]);

//return 0;
for(int i=0;i<qn;++i)
{
    int cp=0,cn=0,z=0,aq=q[i][0],bq=q[i][1],tq=q[i][2];
    for(int j=0;j<pn;++j)
    {
        int a=p[j][0],b=p[j][1],t=p[j][2];
        if(a<=aq&&bq<=b&&abs(t)<=tq){
            z+=t;
            if(t<0)
            {
                ++cn;
            }
            else
            {
                ++cp;
            }
        }
    }
    if(cn<cp)z-=tq;
    printf("%d\n",-z);
}
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:11:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | int main(){scanf("%d%d%s",&n,&Q,s+1);
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:14:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 | for(int i=1,a,b;i<=Q;++i){scanf("%s%d",op,&a);
      |                           ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:15:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     if(*op=='q'){scanf("%d",&b);q[qn][0]=a,q[qn][1]=--b,q[qn][2]=i;++qn;}
      |                  ~~~~~^~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5071 ms 10644 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2560 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 3897 ms 13352 KB Output is correct
6 Execution timed out 5012 ms 14152 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Execution timed out 5037 ms 12448 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 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 5071 ms 10644 KB Time limit exceeded
9 Halted 0 ms 0 KB -