Submission #1039584

#TimeUsernameProblemLanguageResultExecution timeMemory
1039584trucmaiGrowing Trees (BOI11_grow)C++17
10 / 100
98 ms7248 KiB
#include <bits/stdc++.h> #ifdef LOCAL #include "/home/trcmai/code/tools.h" #define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl; #else #define debug(x...) #endif using namespace std; #define all(a) a.begin(), a.end() #define ll long long #define endl '\n' const int N = 1e6 + 6, LOG = 27, MOD = 1e9 + 7; const ll INF = 1e18; int n,q; namespace segtree{ int n; vector<ll>tr,lz; void init(int sz){ n = sz; tr.resize(4*n + 3,0); lz.resize(4*n + 3,0); } void push(int i){ if(!lz[i]) return; tr[2*i] += lz[i]; lz[2*i] += lz[i]; tr[2*i + 1] += lz[i]; lz[2*i + 1] += lz[i]; lz[i] = 0; } void update(int i,int l,int r,int ql,int qr,ll val){ if(l > qr || r < ql) return; if(ql <= l && r <= qr){ lz[i] += val; tr[i] += val; return; } push(i); int m = (r+l) >> 1; update(2*i,l,m,ql,qr,val); update(2*i+1,m+1,r,ql,qr,val); tr[i] = max(tr[2*i],tr[2*i+1]); } ll get(int i,int l,int r,int ql,int qr){ if(l > qr || r < ql) return 0; if(ql <= l && r <= qr) return tr[i]; int m = (r+l) >> 1; push(i); ll left = get(2*i,l,m,ql,qr); ll right = get(2*i+1,m+1,r,ql,qr); return max(left,right); } int walk(int i,int l,int r,ll val){ if(l == r) return (tr[i] >= val ? l : -1); push(i); int m = (r+l) >> 1; if(tr[2*i] >= val) return walk(2*i,l,m,val); else if(tr[2*i + 1] >= val) return walk(2*i + 1,m + 1,r,val); else return -1; } void update(int l,int r,ll val){ update(1,1,n,l,r,val); } ll fval(int pos){ return get(1,1,n,pos,pos); } int walk(ll val){ return walk(1,1,n,val); } } signed main() { cin.tie(0)->sync_with_stdio(0); //freopen("sol.out","w",stdout); auto solver=[&](){ cin>>n>>q; segtree::init(n); vector<int>a(n + 1); for(int i = 1;i <= n;++i) cin>>a[i]; sort(a.begin() + 1,a.end()); for(int i = 1;i <= n;++i) segtree::update(i,i,a[i]); while(q--){ char t; cin>>t; if(t == 'F'){ ll tot,val; cin>>tot>>val; // cerr<<"QUERY UPDATE: "<<tot<<" "<<val<<endl; int l = segtree::walk(val); if(l == -1) continue; int nxt = min(n, int(l + tot - 1)); ll last_val = segtree::fval(nxt); int sz = nxt - l + 1; int ff = segtree::walk(last_val); //update first range int b = nxt - ff + 1; int u = sz - b; segtree::update(l,l + u - 1,1); //update second range int l2 = segtree::walk(last_val + 1); if(l2 == -1) l2 = n; else --l2; segtree::update(l2 - b + 1,l2,1); //cerr<<"RANGE UPDATE: "<<l<<" "<<l + tot - 1<<endl; //for(int i = 1;i <= n;++i) // cerr<<segtree::fval(i)<<" \n"[i == n]; //cerr<<endl; }else{ ll u,v; cin>>u>>v; // cerr<<"QUERY ANS: "<<u<<" "<<v<<endl; int l = segtree::walk(u); int r = segtree::walk(v + 1); if(l == -1 || r == -1) cout<< 0<<endl; else cout<< r - l << endl; // cerr<<"RANGE ANS: "<<l<<" "<<r<<endl; } } }; int t = 1; // cin>>t; while (t--) solver(); }
#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...