Submission #518319

#TimeUsernameProblemLanguageResultExecution timeMemory
518319CSQ31Street Lamps (APIO19_street_lamps)C++17
100 / 100
1314 ms37088 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; #define sz(a) (int)(a.size()) struct fenwick{ vector<ll>bit; int n; void reset(int i){ for(;i<=n;i+=i&(-i))bit[i]=0; } void upd(int i,int x){ for(;i<=n;i+=i&(-i))bit[i]+=x; } ll query(int i){ ll res = 0; for(;i>0;i-=i&(-i))res+=bit[i]; return res; } fenwick(){} fenwick(int _n){ n = _n; bit.assign(n+1,0); } }sum,num,f; struct line{ int tl,tr,ql,qr; line(){} line(int _tl,int _tr,int _ql,int _qr){ tl = _tl; tr = _tr; ql = _ql; qr = _qr; } };vector<line>lines; struct qq{ int l,r,t; qq(){}; qq(int _l,int _r,int _t):l(_l),r(_r),t(_t){} };vector<qq>que; const int MAXN = 3e5+5; line st[MAXN]; int n,q,cnt = 0,ans[MAXN]; set<int>pos; //position of line heads vector<array<int,2>>a; /* * for(int i=1;i<=q;i++){ for(auto q:que[i]){ for(auto y:lines){ if(y.tl <= i && y.ql <= q.l && q.r <= y.qr){ ans[q.i]+=min(y.tr+1,i) - y.tl; } } } } * */ void solve(int s,int t){ if(s == t)return; int mid = (s+t)/2; solve(s,mid); solve(mid+1,t); vector<array<int,2>>add,ask; for(int i=s;i<=mid;i++){ int x = a[i][1]; if(x >= 0){ add.push_back({lines[x].tl,x}); add.push_back({lines[x].tr+1,x}); } } for(int i=mid+1;i<=t;i++){ int x = a[i][1]; if(x < 0){ x++; x*=-1; ask.push_back({que[x].t,x}); } } sort(add.begin(),add.end()); sort(ask.begin(),ask.end()); /* if(t==3){ cout<<"ranges"<<'\n'; cout<<s<<" "<<mid<<" "<<t<<'\n'; cout<<"add"<<'\n'; for(auto x:add)cout<<x[0]<<" "<<x[1]<<'\n'; cout<<"ask"<<'\n'; for(auto x:ask)cout<<x[0]<<" "<<x[1]<<'\n'; }*/ int ptr = -1; for(auto x:ask){ while(ptr+1 < sz(add) && add[ptr+1][0] <= x[0]){ ptr++; int id = add[ptr][1]; if(lines[id].tl == add[ptr][0]){ //add a line into the tl<=t<=tr case sum.upd(lines[id].qr,lines[id].tl); num.upd(lines[id].qr,1); }else{ //delete a line from tl<=t<r case then add into tl<=tr<t case sum.upd(lines[id].qr,-lines[id].tl); num.upd(lines[id].qr,-1); f.upd(lines[id].qr,lines[id].tr - lines[id].tl + 1); } } int y = x[1]; ans[y]+= f.query(n) - f.query(que[y].r-1); /* if(t==3){ cout<<f.query(n)<<" "<<f.query(que[y].r-1)<<'\n'; cout<<que[y].r-1<<" "<<num.query(n)<<" "<<num.query(n) - num.query(que[y].r-1)<<'\n'; }*/ ans[y] += (num.query(n) - num.query(que[y].r-1)) * (que[y].t) - (sum.query(n) - sum.query(que[y].r-1)); } for(int i=0;i<=ptr;i++){ int id = add[i][1]; sum.reset(lines[id].qr); num.reset(lines[id].qr); f.reset(lines[id].qr); } } int main() { ios_base::sync_with_stdio(0);cin.tie(0); string s = "0",ss; cin>>n>>q>>ss; s+=ss; for(int i=1;i<=n;i++){ if(s[i] == '0')continue; int j = i; while(j+1<=n && s[j+1] == '1')j++; st[i] = line(0,0,i,j); pos.insert(i); i = j; } for(int i=1;i<=q;i++){ string u; cin>>u; if(u == "toggle"){ int x; cin>>x; if(s[x] == '0'){ s[x] = '1'; pos.insert(x); st[x] = line(i,i,x,x); auto it = pos.upper_bound(x); int v = 0; if(it != pos.end() && st[*it].ql == x+1){ //new line segment on right side with x as head v = *it; st[v].tr = i-1; lines.push_back(st[v]); //cout<<st[v].tl<<" "<<st[v].tr<<" "<<st[v].ql<<" "<<st[v].qr<<'\n'; st[x] = line(i,i,x,st[v].qr); pos.erase(it); } it = pos.lower_bound(x); if(it == pos.begin())continue; it--; if(st[*it].qr == x-1){ //new line segment on left side v = *it; st[v].tr = i-1; lines.push_back(st[v]); int L = st[v].ql; st[L] = line(i,i,L,st[x].qr); pos.erase(x); } }else{ s[x] = '0'; auto it = pos.upper_bound(x); it--; int v = *it; if(st[v].qr >=x){ //destroy a segment st[v].tr = i-1; lines.push_back(st[v]); if(st[v].qr > x){ //line seg on right pos.insert(x+1); st[x+1] = line(i,i,x+1,st[v].qr); } if(v != x)st[v] = line(i,i,st[v].ql,x-1); //line seg on left } pos.erase(x); } }else{ int l,r; cin>>l>>r; que.push_back(qq(l,r-1,i)); cnt++; a.push_back({l,-cnt}); } } for(int i=1;i<=n;i++){ if(s[i] == '1' && (!i || s[i-1] == '0')){ st[i].tr = q; lines.push_back(st[i]); } } for(int i=0;i<sz(lines);i++){ a.push_back({lines[i].ql,i}); } //for(auto x:lines)cout<<x.tl<<" "<<x.tr<<" "<<x.ql<<" "<<x.qr<<'\n'; sort(a.begin(),a.end(),[&](array<int,2> i,array<int,2> j){ if(i[0] == j[0])return j[1] < i[1]; return i[0] < j[0]; } ); sum = fenwick(n); num = fenwick(n); f = fenwick(n); /* cout<<"LINES"<<'\n'; for(auto x:lines)cout<<x.tl<<" "<<x.tr<<" "<<x.ql<<" "<<x.qr<<'\n'; for(auto x:a)cout<<x[0]<<" "<<x[1]<<'\n'; * */ solve(0,sz(a)-1); for(int i=0;i<cnt;i++)cout<<ans[i]<<'\n'; } /* 5 8 01010 toggle 1 toggle 1 toggle 1 toggle 1 query 1 3 toggle 1 query 1 2 query 1 3 */
#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...