Submission #624508

#TimeUsernameProblemLanguageResultExecution timeMemory
624508kakayoshiGrowing Trees (BOI11_grow)C++17
100 / 100
135 ms2952 KiB
#include <bits/stdc++.h> using namespace std; #define forw(i,a,b) for(int i=a;i<=b;i++) #define forb(i,a,b) for(int i=a;i>=b;i--) #define fi first #define se second #define pb push_back #define all(a) a.begin(),a.end() #define getbit(mask,i) ((mask>>i)&1) typedef long long int ll; const ll maxN=5e5+5; const ll mod=1e9+7; const ll oo=1e18; struct fenwick { int n; vector <int> fen; fenwick(int _n=1e5) { n=_n; fen.assign(n+5,0); } void update(int pos, int val) { for(;pos<=n;pos+=pos&-pos) fen[pos]+=val; return; } void update(int l, int r, int val) { update(l,val); update(r+1,-val); return; } int get(int pos) { int ans=0; for(;pos;pos-=pos&-pos) ans+=fen[pos]; return ans; } }fen; int n,q,a[maxN]; int find_pos(int val) { int l=1; int r=n; int ans=n+1; while (l<=r) { int mid=(l+r)/2; if (fen.get(mid)>=val) { ans=mid; r=mid-1; } else l=mid+1; } return ans; } void solve() { cin>>n>>q; forw(i,1,n) cin>>a[i]; sort(a+1,a+1+n); forw(i,1,n) fen.update(i,i,a[i]); while (q--) { char c; cin>>c; if (c=='F') { int c,h; cin>>c>>h; int l=find_pos(h); if (l==n+1) continue; c=min(c,n-l+1); int r=l+c-1; if (r<n && fen.get(r)==fen.get(r+1)) { h=fen.get(r); int pos=find_pos(h); int add=r-pos+1; r=pos-1; fen.update(l,r,1); pos=find_pos(h+1); fen.update(pos-add,pos-1,1); } else fen.update(l,r,1); } else { int l,r; cin>>l>>r; cout<<find_pos(r+1)-find_pos(l)<<"\n"; } } } int main() { ios::sync_with_stdio(0); cin.tie(0); //freopen("test.inp","r",stdin); //freopen("test.out","w",stdout); solve(); return 0; }
#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...