Submission #257876

#TimeUsernameProblemLanguageResultExecution timeMemory
257876daniel920712Street Lamps (APIO19_street_lamps)C++14
100 / 100
971 ms225020 KiB
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <set> #include <utility> using namespace std; set < pair < int , int > > how; struct A { int l,r; int nxl,nxr,nxt; int con; }Node[80000005]; int now=1; char temp[15]; char all[300005]; int N; int Find(int x,int y,int here) { if(here<0) return 0; int t; if(Node[here].nxt==-2) { t=Node[here].con; if(Node[here].l==y&&Node[here].r==y) return t; else if(y<=(Node[here].l+Node[here].r)/2) t+=Find(x,y,Node[here].nxl); else t+=Find(x,y,Node[here].nxr); } else { t=Node[here].con; t+=Find(x,y,Node[here].nxt); if(Node[here].l==x&&Node[here].r==x) return t; else if(x<=(Node[here].l+Node[here].r)/2) t+=Find(x,y,Node[here].nxl); else t+=Find(x,y,Node[here].nxr); } return t; } void build(int l,int r,int con,int here) { Node[here].l=l; Node[here].r=r; Node[here].nxt=con; Node[here].nxl=-1; Node[here].nxr=-1; Node[here].con=0; } void cha(int l1,int r1,int l2,int r2,int con,int here) { int t; if(Node[here].nxt==-2) { if(Node[here].l==l2&&Node[here].r==r2) { Node[here].con+=con; return ; } if(r2<=(Node[here].l+Node[here].r)/2) { if(Node[here].nxl==-1) { Node[here].nxl=now++; build(Node[here].l,(Node[here].l+Node[here].r)/2,-2,Node[here].nxl); } cha(l1,r1,l2,r2,con,Node[here].nxl); } else if(l2>(Node[here].l+Node[here].r)/2) { if(Node[here].nxr==-1) { Node[here].nxr=now++; build((Node[here].l+Node[here].r)/2+1,Node[here].r,-2,Node[here].nxr); } cha(l1,r1,l2,r2,con,Node[here].nxr); } else { if(Node[here].nxl==-1) { Node[here].nxl=now++; build(Node[here].l,(Node[here].l+Node[here].r)/2,-2,Node[here].nxl); } if(Node[here].nxr==-1) { Node[here].nxr=now++; build((Node[here].l+Node[here].r)/2+1,Node[here].r,-2,Node[here].nxr); } cha(l1,r1,l2,(Node[here].l+Node[here].r)/2,con,Node[here].nxl); cha(l1,r1,(Node[here].l+Node[here].r)/2+1,r2,con,Node[here].nxr); } } else { if(Node[here].l==l1&&Node[here].r==r1) { if(Node[here].nxt==-1) { Node[here].nxt=now++; build(0,300001,-2,Node[here].nxt); } cha(l1,r1,l2,r2,con,Node[here].nxt); return; } if(r1<=(Node[here].l+Node[here].r)/2) { if(Node[here].nxl==-1) { Node[here].nxl=now++; build(Node[here].l,(Node[here].l+Node[here].r)/2,-1,Node[here].nxl); } cha(l1,r1,l2,r2,con,Node[here].nxl); } else if(l1>(Node[here].l+Node[here].r)/2) { if(Node[here].nxr==-1) { Node[here].nxr=now++; build((Node[here].l+Node[here].r)/2+1,Node[here].r,-1,Node[here].nxr); } cha(l1,r1,l2,r2,con,Node[here].nxr); } else { if(Node[here].nxl==-1) { Node[here].nxl=now++; build(Node[here].l,(Node[here].l+Node[here].r)/2,-1,Node[here].nxl); } if(Node[here].nxr==-1) { Node[here].nxr=now++; build((Node[here].l+Node[here].r)/2+1,Node[here].r,-1,Node[here].nxr); } cha(l1,(Node[here].l+Node[here].r)/2,l2,r2,con,Node[here].nxl); cha((Node[here].l+Node[here].r)/2+1,r1,l2,r2,con,Node[here].nxr); } } } int main() { //freopen("17","rt",stdin); int M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok; scanf("%d %d",&N,&M); scanf("%s",all+1); build(0,300001,-1,0); l=1; r=0; for(i=1;i<=N;i++) { if(all[i]=='1') r=i; else { if(r>=l) { how.insert(make_pair(l,r)); cha(l,r+1,l,r+1,M,0); } l=i+1; r=i; } } if(r>=l) { how.insert(make_pair(l,r)); cha(l,r+1,l,r+1,M,0); } for(i=1;i<=M;i++) { scanf("%s",temp); if(temp[0]=='t') { scanf("%d",&where); if(all[where]=='0') { if(how.empty()) { cha(where,where,where+1,where+1,M-i,0); how.insert(make_pair(where,where)); all[where]=(1-(all[where]-'0'))+'0'; continue; } auto a=how.lower_bound(make_pair(where+1,where)); auto b=prev(a); //printf("aa\n"); r1=where; l2=where+1; if(a==how.end()||all[where+1]=='0') r2=where+1; else r2=a->second+1; if(a==how.begin()||all[where-1]=='0') l1=where; else l1=b->first; if(r2!=where+1) how.erase(a); if(l1!=where) how.erase(b); if(r2-1>=l1) how.insert(make_pair(l1,r2-1)); //printf("%d %d %d %d\n",l1,r1,l2,r2); cha(l1,r1,l2,r2,M-i,0); } else { auto a=prev(how.lower_bound(make_pair(where+1,where))); l1=a->first; r1=where; l2=where+1; r2=a->second+1; how.erase(a); if(r1-1>=l1) how.insert(make_pair(l1,r1-1)); if(r2-1>=l2) how.insert(make_pair(l2,r2-1)); cha(l1,r1,l2,r2,i-M,0); } all[where]=(1-(all[where]-'0'))+'0'; } else { scanf("%d %d",&l,&r); ok=1; if(how.lower_bound(make_pair(l+1,r))!=how.begin()&&prev(how.lower_bound(make_pair(l+1,r)))->first<=l&&prev(how.lower_bound(make_pair(l+1,r)))->second>=r-1) ok=1; else ok=0; printf("%d\n",max(Find(l,r,0)-(M-i)*ok,0)); } } return 0; }

Compilation message (stderr)

street_lamps.cpp: In function 'void cha(int, int, int, int, int, int)':
street_lamps.cpp:51:9: warning: unused variable 't' [-Wunused-variable]
     int t;
         ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:143:11: warning: unused variable 't' [-Wunused-variable]
     int M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
           ^
street_lamps.cpp:143:31: warning: unused variable 'j' [-Wunused-variable]
     int M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
                               ^
street_lamps.cpp:143:33: warning: unused variable 'k' [-Wunused-variable]
     int M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
                                 ^
street_lamps.cpp:143:41: warning: unused variable 'ok1' [-Wunused-variable]
     int M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
                                         ^~~
street_lamps.cpp:143:47: warning: unused variable 'ok2' [-Wunused-variable]
     int M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
                                               ^~~
street_lamps.cpp:144:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&M);
     ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:145:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",all+1);
     ~~~~~^~~~~~~~~~~~
street_lamps.cpp:171:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",temp);
         ~~~~~^~~~~~~~~~~
street_lamps.cpp:174:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&where);
             ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:215:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d",&l,&r);
             ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...