Submission #432953

#TimeUsernameProblemLanguageResultExecution timeMemory
432953TLP39Street Lamps (APIO19_street_lamps)C++14
40 / 100
359 ms16484 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<ll,ll> pll; struct query{ int t,u,v; }; const int big=1000000000; int n,q; bool on[300010]; int last_open[300010]={}; char s[300010]; int res[300010]={}; int ans; int seg[1200040]={}; int x,y; vector<query> vec; void upd(int v,int l,int r,int pos,int val) { if(l==r) { seg[v]=val; return; } int mid=(l+r)>>1; if(mid>=pos) upd(v<<1,l,mid,pos,val); else upd(1+(v<<1),mid+1,r,pos,val); seg[v]=max(seg[v<<1],seg[1+(v<<1)]); } int que(int v,int l,int r,int st,int ed) { if(st>ed) return -1; if(l==st && r==ed) return seg[v]; int mid=(l+r)>>1; return max(que(v<<1,l,mid,st,min(mid,ed)),que(1+(v<<1),mid+1,r,max(mid+1,st),ed)); } void solve_2() { int temp; for(int i=0;i<n;i++) on[i+1]=(s[i]=='1'); for(int i=0;i<q;i++) { if(vec[i].t==1) { temp=vec[i].u; if(on[temp]) printf("%d\n",res[temp]+(i+1-last_open[temp])); else printf("%d\n",res[temp]); } else { temp=vec[i].u; if(on[temp]) { on[temp]=false; res[temp]+=((i+1)-last_open[temp]); } else { on[temp]=true; last_open[temp]=i+1; } } } } void solve_3() { for(int i=0;i<1200040;i++) seg[i]=big; int temp,t1,t2; for(int i=0;i<n;i++) { if(s[i]=='1') upd(1,1,n,i+1,0); } for(int i=0;i<q;i++) { if(vec[i].t==1) { t1=vec[i].u; t2=vec[i].v; temp=que(1,1,n,t1,t2-1); if(temp==big) printf("0\n"); else printf("%d\n",(i+1)-temp); } else { t1=vec[i].u; upd(1,1,n,t1,i+1); } } } int main() { bool ch=true; scanf("%d %d",&n,&q); scanf("%s",s); char tt[10]; for(int i=0;i<q;i++) { scanf("%s",tt); if(tt[0]=='q') { scanf("%d %d",&x,&y); vec.push_back({1,x,y}); if(y-x>1) ch=false; } else { scanf("%d",&x); vec.push_back({2,x,x}); } } if(ch) solve_2(); else solve_3(); }

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |     scanf("%s",s);
      |     ~~~~~^~~~~~~~
street_lamps.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         scanf("%s",tt);
      |         ~~~~~^~~~~~~~~
street_lamps.cpp:108:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |             scanf("%d %d",&x,&y);
      |             ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:114:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |             scanf("%d",&x);
      |             ~~~~~^~~~~~~~~
#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...