Submission #555079

#	Time	Username	Problem	Language	Result	Execution time	Memory
555079		new_acc	Growing Trees (BOI11_grow)	C++14	100 / 100	206 ms	11504 KiB

grow

#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<<1)]+=lazy[v],lazy[(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,seg1[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 seg2[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,seg1[i]=-1;
    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);
            c=min(c,n-curr1+1);
            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();
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10