Submission #1213441

#TimeUsernameProblemLanguageResultExecution timeMemory
1213441orzorzorzGrowing Trees (BOI11_grow)C++20
0 / 100
66 ms2372 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ff first #define ss second #define all(x) x.begin(), x.end() const int mxN=1e5+1; ll bit[mxN+1], a[mxN+1]; int n, m; void upd(int pos, ll val) { for(; pos<=mxN; pos+=pos&-pos) { bit[pos]+=val; } } ll qry(int pos) { ll res=0; for(; pos; pos-=pos&-pos) { res+=bit[pos]; } return res; } int f(ll val) { int l=1, r=n; while(l<=r) { int mid=(l+r)/2; if(qry(mid)>=val) { r=mid-1; } else { l=mid+1; } } return l; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for(int i=1; i<=n; i++) { cin>>a[i]; } sort(a+1, a+n+1); for(int i=1; i<=n; i++) { upd(i, a[i]); upd(i+1, -a[i]); } for(int i=0; i<m; i++) { char ty; cin>>ty; if(ty=='F') { int c, h; cin>>c>>h; int left=f(h), right=left+c-1; if(left==n+1) continue; if(right>n) { upd(left, 1); upd(n+1, -1); } else if(qry(right)!=qry(right+1)) { upd(left, 1); upd(right+1, -1); } else { ll val=qry(right); int newl=f(val); upd(left, 1); upd(newl, -1); int newr=f(val+1);//[newr-1-count+1 ,newr-1] count is equal to newl-left upd(newr-(newl-left), 1); upd(newr, -1); } } else { ll x, y; cin>>x>>y; int l=f(x), r=f(y+1); if(l==n+1) { cout<<0<<"\n"; } else { r--; cout<<r-l+1<<"\n"; } } } return 0; } //rating below 2400 must be solved orzorzorz
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...