Submission #554999

#TimeUsernameProblemLanguageResultExecution timeMemory
554999new_accGrowing Trees (BOI11_grow)C++14
0 / 100
111 ms10380 KiB
#include<bits/stdc++.h> #define fi first #define se second #define pitem item* using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> vi; typedef vector<ll> vl; const int N=1e6+10; const int SS=1<<19; const int INFi=2e9; const ll INFl=1e13; const ll mod2=998244353; const ll mod=1e9+7; const ll mod3=1000696969; const ll p=70032301; const ull p2=913; const int L=20; int t[N],seg1[(SS<<1)+10],seg2[(SS<<1)+10],lazy[(SS<<1)+10]; void push(int v){ seg1[(v<<1)]+=lazy[v],seg1[(v<<1)+1]+=lazy[v]; seg2[(v<<1)]+=lazy[v],seg2[(v<<1)+1]+=lazy[v]; lazy[v]=0; } void upd(int a,int b,int x,int p=0,int k=SS-1,int v=1){ if(p>b or k<a) return; if(p>=a and k<=b){ if(seg2[v]==INFi) seg2[v]=0; lazy[v]+=x,seg1[v]+=x,seg2[v]+=x; return; } push(v); upd(a,b,x,p,(p+k)>>1,(v<<1)),upd(a,b,x,((p+k)>>1)+1,k,(v<<1)+1); seg1[v]=max(seg1[v<<1],seg1[(v<<1)+1]); seg2[v]=min(seg2[v<<1],seg2[(v<<1)+1]); } int Query1(int x,int v=1){ if(v>SS) return v-SS; push(v); if(seg1[(v<<1)]>=x) return Query1(x,(v<<1)); else return Query1(x,(v<<1)+1); } int Query2(int x,int v=1){ if(v>SS) return v-SS; push(v); if(seg2[(v<<1)+1]<=x) return Query2(x,(v<<1)+1); else return Query2(x,(v<<1)); } int Query3(int x,int p=0,int k=SS-1,int v=1){ if(p==k) return seg1[v]; push(v); int sr=(p+k)>>1; if(x>sr) return Query3(x,sr+1,k,(v<<1)+1); else return Query3(x,p,sr,(v<<1)); } void solve(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>t[i]; for(int i=1;i<=(SS<<1);i++) seg2[i]=INFi; sort(t+1,t+1+n); for(int i=1;i<=n;i++) upd(i,i,t[i]); for(int i=1;i<=m;i++){ char a; cin>>a; if(a=='F'){ int b,c; cin>>c>>b; if(seg1[1]<b) continue; int curr1=Query1(b),val=seg1[curr1+SS]; int curr2=Query2(val); if(curr2-curr1+1>=c) upd(curr2-c+1,curr2,1); else{ c-=(curr2-curr1+1); int val2=Query3(curr2+c); int wsk1=Query1(val2),dl=curr2+c-wsk1+1,wsk2=Query2(val2); upd(wsk2-dl+1,wsk2,1),upd(curr2+1,wsk1-1,1),upd(curr1,curr2,1); } }else{ int b,c; cin>>b>>c; if(b>seg1[1] or c<seg2[1]){ cout<<0<<"\n"; continue; } cout<<Query2(c)-Query1(b)+1<<"\n"; } } } int main(){ ios_base::sync_with_stdio(0),cin.tie(0); int tt=1; while(tt--) solve(); }
#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...