Submission #1215500

#TimeUsernameProblemLanguageResultExecution timeMemory
1215500emptypringlescanFish 2 (JOI22_fish2)C++17
13 / 100
55 ms63928 KiB
#include <bits/stdc++.h> using namespace std; bool st3; int n,q; long long arr[100005]; struct node{ int s,e,m; pair<long long,int> val; node *l,*r; node(int S, int E){ s=S; e=E; m=(s+e)/2; if(s!=e){ l=new node(s,m); r=new node(m+1,e); val=max(l->val,r->val); } else val={arr[s],s}; } pair<long long,int> query(int S, int E){ if(S<=s&&e<=E) return val; if(E<=m) return l->query(S,E); else if(S>m) return r->query(S,E); else return max(l->query(S,m),r->query(m+1,E)); } } *root; vector<pair<int,int> > bad; pair<int,int> nxt[2][100005]; pair<pair<int,int>,int> twok[2][20][100005]; long long pref[100005]; void recons(){ pref[0]=0; for(int i=1; i<=n; i++) pref[i]=pref[i-1]+arr[i]; bad.clear(); vector<pair<long long,int> > mono={{1e9,0}}; for(int i=1; i<=n; i++){ while(!mono.empty()&&mono.back().first<arr[i]){ if(mono.back().second<i-1&&pref[i-1]-pref[mono.back().second]<min(arr[i],mono.back().first)){ bad.push_back({mono.back().second+1,i-1}); } mono.pop_back(); } if(mono.back().second<i-1&&pref[i-1]-pref[mono.back().second]<min(arr[i],mono.back().first)){ bad.push_back({mono.back().second+1,i-1}); } mono.push_back({arr[i],i}); } while(!mono.empty()){ if(mono.back().second<n&&pref[n]-pref[mono.back().second]<mono.back().first){ bad.push_back({mono.back().second+1,n}); } mono.pop_back(); } //for(auto i:bad) cout << i.first << ' ' << i.second << '\n'; for(int i=0; i<=n; i++) nxt[0][i]=nxt[1][i]={-1,-1}; for(auto i:bad){ if(i.first>1){ if(nxt[0][i.first-1].first==-1||nxt[0][i.first-1].second<i.second) nxt[0][i.first-1]=i; } if(i.second<n){ if(nxt[1][i.second+1].first==-1||nxt[1][i.second+1].first>i.first) nxt[1][i.second+1]=i; } } pair<int,int> cur={-1,-1}; for(int i=1; i<=n; i++){ if(nxt[1][i].first==-1) nxt[1][i]=cur; else cur=nxt[1][i]; } cur={-1,-1}; for(int i=n; i>0; i--){ if(nxt[0][i].first==-1) nxt[0][i]=cur; else cur=nxt[0][i]; } if(!st3){ for(int i=0; i<2; i++) for(int j=0; j<20; j++) for(int k=0; k<=n; k++) twok[i][j][k]={{-1,-1},-1}; for(int i=1; i<=n; i++){ twok[0][0][i]={nxt[0][i],nxt[0][i].second-nxt[0][i].first+1}; twok[1][0][i]={nxt[1][i],nxt[1][i].second-nxt[1][i].first+1}; } for(int i=0; i<19; i++){ for(int j=1; j<=n; j++){ if(twok[0][i][j].first.first!=-1){ twok[0][i+1][j].first=twok[0][i][twok[0][i][j].first.second+1].first; twok[0][i+1][j].second=twok[0][i][j].second+twok[0][i][twok[0][i][j].first.second+1].second; } if(twok[1][i][j].first.first!=-1){ twok[1][i+1][j].first=twok[1][i][twok[1][i][j].first.first-1].first; twok[1][i+1][j].second=twok[1][i][j].second+twok[1][i][twok[1][i][j].first.first-1].second; } } } } } int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i=1; i<=n; i++) cin >> arr[i]; cin >> q; if(q<1000) st3=true; else{ st3=false; root=new node(1,n); } recons(); while(q--){ int cmd; cin >> cmd; if(cmd==1){ int x; long long y; cin >> x >> y; arr[x]=y; recons(); } else{ int a,b; cin >> a >> b; if(!st3){ int big=root->query(a,b).second; int tbad=0; int cur=big; for(int i=19; i>=0; i--){ if(twok[0][i][cur].first.first!=-1&&twok[0][i][cur].first.second<=b){ tbad+=twok[0][i][cur].second; cur=twok[0][i][cur].first.second+1; } } if(twok[0][0][cur].first.first!=-1&&twok[0][0][cur].first.first<=b){ assert(twok[0][0][cur].first.second>b); tbad+=b-twok[0][0][cur].first.first+1; } cur=big; for(int i=19; i>=0; i--){ if(twok[1][i][cur].first.first!=-1&&twok[1][i][cur].first.first>=a){ tbad+=twok[1][i][cur].second; cur=twok[1][i][cur].first.first-1; } } if(twok[1][0][cur].first.first!=-1&&twok[1][0][cur].first.second>=a){ assert(twok[0][0][cur].first.first<a); tbad+=twok[1][0][cur].first.second-a+1; } cout << b-a+1-tbad << '\n'; } else{ int wall=a; for(int i=a; i<=b; i++){ if(arr[i]-pref[i-1]+pref[a-1]>0) wall=i; } a=wall; wall=b; for(int i=b; i>=a; i--){ if(arr[i]-pref[b]+pref[i]>0) wall=i; } b=wall; pair<long long,int> big={-1,-1}; for(int i=a; i<=b; i++) big=max(big,make_pair(arr[i],i)); int tbad=0; int cur=big.second; while(cur<=b){ if(nxt[0][cur].first==-1) break; if(nxt[0][cur].second<=b){ tbad+=nxt[0][cur].second-nxt[0][cur].first+1; cur=nxt[0][cur].second+1; } else if(nxt[0][cur].first<=b){ tbad+=b-nxt[0][cur].first+1; break; } else break; } cur=big.second; while(cur>=a){ if(nxt[1][cur].first==-1) break; if(nxt[1][cur].first>=a){ tbad+=nxt[1][cur].second-nxt[1][cur].first+1; cur=nxt[1][cur].first-1; } else if(nxt[1][cur].second>=a){ tbad+=nxt[1][cur].second-a+1; break; } else break; } cout << b-a+1-tbad << '\n'; } } } }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...