Submission #538312

#	Time	Username	Problem	Language	Result	Execution time	Memory
538312		perchuts	Growing Trees (BOI11_grow)	C++17	0 / 100	1092 ms	39500 KiB

grow

#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

int seg[10*maxn], v[maxn];
int n,m,add;

struct lazySeg{
    vector<pair<int,ii>>operations;
    int gain, loss;
}lazy[10*maxn];// {comes in, comes out}

void build(int i=1, int l=1, int r=n){
    if(l==r){
        seg[i] = v[l];
        return;
    }
    int md = (l+r)>>1;
    build(2*i,l,md);
    build(2*i+1,md+1,r);
    seg[i] = seg[2*i] + seg[2*i+1];
}

int query(int i,int l,int r,int x,int y);

void insertLazy(int i,int l,int r){
    if(sz(lazy[i].operations)==0)return;
    vector<pair<int,ii>>tmp = lazy[i].operations;
    lazy[i].operations.clear();
    for(auto [tot,p]:tmp){
        auto [x,y] = p;
        if(l!=x)lazy[i].gain += query(1,1,n,l-1,l-1);
        if(r!=y)lazy[i].loss += query(1,1,n,r,r);
        else{
            add = min(query(1,1,n,y,y), tot - query(1,1,n,x,y-1));
            lazy[i].loss += add;
        }
        if(l!=r){
            lazy[2*i].operations.pb({tot,{x,y}});
            lazy[2*i+1].operations.pb({tot,{x,y}});
        }
        seg[i] += lazy[i].gain - lazy[i].loss;
        lazy[i].gain = lazy[i].loss = 0;
    }
}

int query(int i,int l,int r,int x,int y){
    insertLazy(i,l,r);
    if(l>y||r<x)return 0;
    if(x<=l&&r<=y)return seg[i];
    int md = (l+r)/2;
    return query(2*i,l,md,x,y) + query(2*i+1,md+1,r,x,y);
}


void update(int i,int l,int r,int x,int y,int tot){
    insertLazy(i,l,r);
    if(l>y||r<x)return;
    if(x<=l&&r<=y){
        lazy[i].operations.pb({tot,{x,y}});
        insertLazy(i,l,r);
        return;
    }
    int md = (l+r)/2;
    update(2*i,l,md,x,y,tot);
    update(2*i+1,md+1,r,x,y,tot);
    seg[i] = seg[2*i] + seg[2*i+1];
}
void update(int i,int l,int r,int x,int tot){
    insertLazy(i,l,r);
    if(l>x||r<x)return;
    if(l==r){
        seg[i] += tot;
        return;
    }
    int md = (l+r)/2;
    update(2*i,l,md,x,tot);
    update(2*i+1,md+1,r,x,tot);
    seg[i] = seg[2*i] + seg[2*i+1];
}

int search(int c,int h1){
    int l = h1, r = 2*n, answer = r;
    while(l<=r){
        int md = l + (r-l+1)/2;
        if(query(1,1,n,h1,md)>=c)answer = md, r = md-1;
        else l = md+1;
    }
    return answer;
}

int main(){_
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        int x;cin>>x;
        v[x]++;
    }    
    build();
    while(m--){
        char o;cin>>o;
        if(o=='F'){
            int c,h;cin>>c>>h;
            if(h>2e5+10)continue;
            int h2 = search(c,h);
            update(1,1,n,h,h2,c);
            update(1,1,n,h2+1,add);
        }else{
            int l,r;cin>>l>>r;
            cout<<query(1,1,n,l,r)<<endl;
        }
    }
}

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