Submission #921538

#TimeUsernameProblemLanguageResultExecution timeMemory
921538LCJLYStreet Lamps (APIO19_street_lamps)C++14
20 / 100
5055 ms287064 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ld long double #define show(x,y) cout << y << " " << #x << endl; #define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl; #define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl; #define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl; typedef pair<int,int>pii; inline int combine(int a, int b){ return a+b; } struct node{ int s,e,m; node *l,*r; int v; int lazyUpd,lazySet; bool lset; node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(0),lazyUpd(0),lazySet(0),lset(0){ if(s!=e){ l=new node(s,m); r=new node(m+1,e); } } void self_set(int x){ v=(e-s+1)*x; lset=1; lazySet=x; lazyUpd=0; } void self_add(int x){ if(lset){ self_set(x+lazySet); return; } v+=(e-s+1)*x; lazyUpd+=x; } void forceProp(){ if(s==e) return; if(lazyUpd){ l->self_add(lazyUpd),r->self_add(lazyUpd); lazyUpd=0; } if(lset){ l->self_set(lazySet),r->self_set(lazySet); lazySet=0; lset=0; } } void rangeUpd(int x, int y, int c){ if(x<=s&&y>=e){ self_add(c); return; } forceProp(); if(x<=m)l->rangeUpd(x,y,c); if(y>m)r->rangeUpd(x,y,c); v=combine(l->v,r->v); } void rangeSet(int x, int y, int c){ if(x<=s&&y>=e){ self_set(c); return; } forceProp(); if(x<=m)l->rangeSet(x,y,c); if(y>m)r->rangeSet(x,y,c); v=combine(l->v,r->v); } int query(int x, int y){ if(x<=s&&y>=e){ return v; } forceProp(); if(y<=m)return l->query(x,y); if(x>m)return r->query(x,y); return combine(l->query(x,m),r->query(m+1,y)); } }; int n,q; string s; node st(0,300005); int ans[300005]; typedef pair<pii,pii>pi2; void dnc(int l, int r, vector<pi2>storage, vector<pi2>que){ if(r<=l) return; //show2(l,l,r,r); vector<pi2>lstorage,rstorage; vector<pi2>lque,rque; int mid=(l+r)/2; for(auto it:storage){ if(it.second.first<=mid&&it.second.second>mid){ lstorage.push_back({it.first,{it.second.first,mid}}); rstorage.push_back({it.first,{mid+1,it.second.second}}); } else if(it.second.second<=mid){ lstorage.push_back(it); } else if(it.second.first>mid){ rstorage.push_back(it); } } for(auto it:que){ if(it.second.first<=mid){ lque.push_back(it); } else rque.push_back(it); } sort(lstorage.begin(),lstorage.end()); sort(rque.begin(),rque.end()); st.rangeSet(0,n+5,0); int cur=0; for(auto it:rque){ int lft=it.first.first; int rgt=it.first.second; int index=it.second.second; //show(check,1); while(cur<(int)lstorage.size()){ //show(loop,1); if(lstorage[cur].first.first<=lft){ //show(lstorage[cur].first.secodn,lstorage[cur].first.second); st.rangeUpd(lstorage[cur].first.second,lstorage[cur].first.second,lstorage[cur].second.second-lstorage[cur].second.first+1); cur++; } else{ //show(trigger,1); break; } } //show2(rgt,rgt,n,n); ans[index]+=st.query(rgt,n); } dnc(l,mid,lstorage,lque); dnc(mid+1,r,rstorage,rque); } void solve(){ cin >> n >> q; cin >> s; s="0"+s+"0"; string temp; int l,r; int ptr=0; vector<pi2>que; set<pair<pii,int>>se; vector<pi2>storage; for(int x=1;x<=n;x++){ if(s[x]=='1'){ int cur=x; for(int y=x;y<=n;y++){ if(s[y]=='0') break; cur=y; } se.insert({{cur,x},0LL}); x=cur; } } for(int x=1;x<=q;x++){ cin >> temp; if(temp=="toggle"){ cin >> l; if(s[l]=='1'){ //turn off auto it=se.lower_bound({{l,0LL},0LL}); pair<pii,int>hold=*it; storage.push_back({{hold.first.second,hold.first.first},{hold.second,x-1}}); if(hold.first.second<l){ se.insert({{l-1,hold.first.second},x}); } if(hold.first.first>l){ se.insert({{hold.first.first,l+1},x}); } se.erase(se.find(hold)); s[l]='0'; } else{ //turn on if(s[l-1]=='1'&&s[l+1]=='1'){ auto it=se.lower_bound({{l,0LL},0LL}); pair<pii,int>hold,hold2; hold=*it; it--; hold2=*it; storage.push_back({{hold.first.second,hold.first.first},{hold.second,x-1}}); storage.push_back({{hold2.first.second,hold2.first.first},{hold2.second,x-1}}); se.insert({{hold.first.first,hold2.first.second},x}); se.erase(se.find(hold)); se.erase(se.find(hold2)); } else if(s[l-1]=='1'){ auto it=se.lower_bound({{l,0LL},0LL}); it--; pair<pii,int>hold=*it; storage.push_back({{hold.first.second,hold.first.first},{hold.second,x-1}}); se.insert({{l,hold.first.second},x}); se.erase(se.find(hold)); } else if(s[l+1]=='1'){ auto it=se.lower_bound({{l,0LL},0LL}); pair<pii,int>hold=*it; storage.push_back({{hold.first.second,hold.first.first},{hold.second,x-1}}); se.insert({{hold.first.first,l},x}); se.erase(se.find(hold)); } else{ se.insert({{l,l},x}); } s[l]='1'; } } else{ cin >> l >> r; r--; que.push_back({{l,r},{x,ptr++}}); } } for(auto it:se){ storage.push_back({{it.first.second,it.first.first},{it.second,q}}); } sort(que.begin(),que.end()); dnc(0,q,storage,que); for(int x=0;x<ptr;x++){ cout << ans[x] << "\n"; } } int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); int t=1; //cin >> t; while(t--){ solve(); } }
#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...