Submission #834383

#TimeUsernameProblemLanguageResultExecution timeMemory
834383AntekbStreet Lamps (APIO19_street_lamps)C++17
100 / 100
729 ms195140 KiB
#include<bits/stdc++.h> #define st first #define nd second #define all(x) (x).begin(), (x).end() #define pb push_back #define eb emplace_back #define pp pop_back #define mp make_pair using namespace std; using pii = pair<int, int>; using ll = long long; using vi = vector<int>; using vii = vector<pii>; void debug(){cerr<<"\n";} template<typename H, typename... T> void debug(H h, T... t){ cerr<<h; if(sizeof...(t)){ cerr<<", "; } debug(t...); } #define deb(x...) cerr<<#x<<" = ";debug(x); mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const int N=1<<19; vi todo[N]; int pref[N+N], suf[N+N], L[N+N], R[N+N], siz[N+N], M[N], tim[N+N]; int male[N]; int ans[N], typ[N]; vector<pair<pii, pii> > U[N]; vector<pair<int, pii> > Q[N]; void upd(int v){ int l=v+v, r=v+v+1; if(pref[l]==siz[l])pref[v]=pref[r]+siz[l]; else pref[v]=pref[l]; if(suf[r]==siz[r])suf[v]=suf[l]+siz[r]; else suf[v]=suf[r]; } int tab[N+N]; void add(int v, int c){ for(v+=N; v>0; v>>=1){ tab[v]+=c; } } int sum(int l, int r){ int res=0; for(l+=N, r+=N; l<r; l>>=1, r>>=1){ if(l&1)res+=tab[l++]; if(r&1)res+=tab[--r]; } return res; } void solve(vector<pair<pii, pii> > &V, int l, int r, vector<pair<int, pii> > q, vector<pair<pii, pii> > U){ if(l+1==r){ for(auto i:q){ for(int k=l; k<r; k++){ auto j=V[k]; if(j.st.st<=i.st && j.nd.st>=i.nd.st && j.nd.nd>=i.nd.nd){ ans[i.st]+=j.st.nd; } } } return; } /*deb(l, r); for(int j=l; j<r; j++){ auto i=V[j]; deb(i.st.st,i.st.nd,i.nd.st,i.nd.nd); } deb("b"); for(int j=0; j<U.size(); j++){ auto i=U[j]; deb(i.st.st,i.st.nd,i.nd.st,i.nd.nd); }*/ assert(U.size()==r-l); if(l==r || !q.size())return; int m=(l+r)/2; int t=V[m].st.st; //deb(m, t); vector<pair<int, pii> > QL, QR; for(auto &i:q){ if(i.st<t)QL.pb(i); else QR.pb(i); } vector<pair<pii, pii> > UL, UR; for(auto i:U){ if(i.nd.st<t)UL.pb(i); else UR.pb(i); } int wsk=0; for(auto i:QR){ while(wsk<UL.size() && UL[wsk].st.st>=i.nd.st){ add(UL[wsk].st.nd, UL[wsk].nd.nd); wsk++; } ans[i.st]+=sum(i.nd.nd, N); } wsk=0; for(auto i:QR){ while(wsk<UL.size() && UL[wsk].st.st>=i.nd.st){ add(UL[wsk].st.nd, -UL[wsk].nd.nd); wsk++; } } solve(V, l, m, QL, UL); solve(V, m, r, QR, UR); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, q; cin>>n>>q; string s; cin>>s; for(int i=0; i<n; i++){ siz[N+i]=1; L[N+i]=i; R[N+i]=i+1; suf[N+i]=pref[N+i]=(s[i]-'0'); } for(int i=N-1; i; i--){ siz[i]=siz[i+i]+siz[i+i+1]; L[i]=L[i+i]; M[i]=R[i+i]; if(R[i+i+1]==0)R[i]=R[i+i]; else R[i]=R[i+i+1]; upd(i); } for(int qq=1; qq<=q; qq++){ cin>>s; if(s[0]=='q'){ //deb(qq); typ[qq]=1; int a, b; cin>>a>>b; a--; b--; if(a==b-1){ //deb(a, suf[N+a], tim[N+a]); ans[qq]=male[a]+suf[N+a]*(qq-tim[N+a]); continue; } //[a, b) int v=1; while(v<N){ int m=M[v]; if(m>=b)v=v+v; else if(m<=a)v=v+v+1; else{ int x=m-a, y=b-m; //deb(v, L[v], R[v], suf[v+v], pref[v+v+1], qq-tim[v]);deb(x, y); if(suf[v+v]>=x && pref[v+v+1]>=y){ ans[qq]+=qq-tim[v]; } Q[v].eb(qq, mp(x, y)); break; } } } else{ int v; cin>>v; v--; if(suf[N+v]){ male[v]+=qq-tim[N+v]; } v+=N; tim[v]=qq; for(int vv=v/2; vv; vv/=2){ U[vv].eb(mp(qq, qq-tim[vv]), mp(suf[vv+vv], pref[vv+vv+1])); } suf[v]^=1; pref[v]^=1; for(v/=2; v; v/=2){ //deb(v, L[v], R[v], suf[v+v], pref[v+v+1], qq-tim[v]); tim[v]=qq; upd(v); } } } for(int v=1; v<N; v++){ if(Q[v].size()){ vector<pair<pii, pii> > UU=U[v]; for(auto &i:UU){ swap(i.st, i.nd); } sort(all(UU)); reverse(all(UU)); sort(all(Q[v]), [](pair<int,pii> a, pair<int, pii> b) {return a.nd>b.nd;}); for(auto i:UU){ //deb(i.st.st, i.st.nd, i.nd.st,i.nd.nd); } for(auto i:Q[v]){ //deb(i.st, i.nd.st,i.nd.nd); } /*int wsk=0; for(auto i:Q[v]){ while(wsk<UU.size() && UU[wsk].st.st>=i.nd.st){ add(UU[wsk].st.nd, UU[wsk].nd.nd); wsk++; } ans[i.st]+=sum(i.nd.nd, N); } wsk=0; for(auto i:Q[v]){ while(wsk<UU.size() && UU[wsk].st.st>=i.nd.st){ add(UU[wsk].st.nd, -UU[wsk].nd.nd); wsk++; } }*/ solve(U[v], 0, U[v].size(), Q[v], UU); } else{ for(auto i:Q[v]){ for(auto j:U[v]){ if(j.st.st<=i.st && j.nd.st>=i.nd.st && j.nd.nd>=i.nd.nd){ ans[i.st]+=j.st.nd; } } } } } for(int i=1; i<=q; i++){ if(typ[i])cout<<ans[i]<<"\n"; } }

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from street_lamps.cpp:1:
street_lamps.cpp: In function 'void solve(std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >&, int, int, std::vector<std::pair<int, std::pair<int, int> > >, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >)':
street_lamps.cpp:77:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |  assert(U.size()==r-l);
      |         ~~~~~~~~^~~~~
street_lamps.cpp:94:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     while(wsk<UL.size() && UL[wsk].st.st>=i.nd.st){
      |           ~~~^~~~~~~~~~
street_lamps.cpp:102:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     while(wsk<UL.size() && UL[wsk].st.st>=i.nd.st){
      |           ~~~^~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:195:13: warning: variable 'i' set but not used [-Wunused-but-set-variable]
  195 |    for(auto i:UU){
      |             ^
street_lamps.cpp:198:13: warning: variable 'i' set but not used [-Wunused-but-set-variable]
  198 |    for(auto i:Q[v]){
      |             ^
#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...