Submission #466380

#	Time	Username	Problem	Language	Result	Execution time	Memory
466380		jli12345	Growing Trees (BOI11_grow)	C++14	100 / 100	281 ms	11204 KiB

grow

#include <bits/stdc++.h>
using namespace std;

void fastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

int N, M;

int arr[100100];

typedef long long ll;

ll stsum[400100], stmin[400100], stmax[400100], addtag[400100];

void pushdown(int node, int l, int mid, int r){
    stsum[node*2] += (mid-l+1)*addtag[node];
    stsum[node*2+1] += (r-mid)*addtag[node];
    stmin[node*2] += addtag[node];
    stmin[node*2+1] += addtag[node];
    stmax[node*2] += addtag[node];
    stmax[node*2+1] += addtag[node];
    addtag[node*2] += addtag[node];
    addtag[node*2+1] += addtag[node];
    addtag[node] = 0;
}

void U(int node, int l, int r, int tl, int tr, ll val){
    if (l > tr || r < tl)
        return;
    if (l >= tl && r <= tr){
        stsum[node] += (r-l+1)*val;
        stmin[node] += val;
        stmax[node] += val;
        addtag[node] += val;
        return;
    }
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    U(node*2, l, mid, tl, tr, val);
    U(node*2+1, mid+1, r, tl, tr, val);
    stsum[node] = stsum[node*2]+stsum[node*2+1];
    stmin[node] = min(stmin[node*2], stmin[node*2+1]);
    stmax[node] = max(stmax[node*2], stmax[node*2+1]);
}

ll Qsum(int node, int l, int r, int tl, int tr){
    if (l > tr || r < tl)
        return 0;
    if (l >= tl && r <= tr){
        return stsum[node];
    }
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    return Qsum(node*2, l, mid, tl, tr)+Qsum(node*2+1, mid+1, r, tl, tr);
}

ll Qlb(int node, int l, int r, int val){ //last index in the range <= val
    if (l == r){
        return l;
    }
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    if (stmin[node*2+1] <= val){
        return Qlb(node*2+1, mid+1, r, val);
    } else {
        return Qlb(node*2, l, mid, val);
    }
}

ll Qrb(int node, int l, int r, int val){ //first index in the range >=
    if (l == r){
        return l;
    }
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    if (stmax[node*2] >= val){
        return Qrb(node*2, l, mid, val);
    } else {
        return Qrb(node*2+1, mid+1, r, val);
    }
}

int main(){
    fastIO();
    cin >> N >> M;
    for (int i = 1; i <= N; i++){
        cin >> arr[i];
    }
    sort(arr+1, arr+1+N);
    for (int i = 1; i <= N; i++){
        U(1, 1, N, i, i, arr[i]);
    }
    /*
    cout << "first: ";
    for (int i = 1; i <= N; i++){
        cout << Qsum(1, 1, N, i, i) << " ";
    }
    cout << "\n";*/
    for (int i = 1; i <= M; i++){
        char k; cin >> k;
        if (k == 'F'){
            int c, h; cin >> c >> h;
            if (stmax[1] < h)
                continue;
            int lpos = Qrb(1, 1, N, h);
            if (lpos+c-1 < N){
                int val = Qsum(1, 1, N, lpos+c-1, lpos+c-1);
                int rpos = Qlb(1, 1, N, val);
                int lrpos = Qrb(1, 1, N, val);
                if (lrpos-1 >= lpos)
                    U(1, 1, N, lpos, lrpos-1, 1);
                int used = lrpos-1-lpos+1;
                if (rpos-(c-used)+1 <= rpos)
                    U(1, 1, N, rpos-(c-used)+1, rpos, 1);
            } else {
                U(1, 1, N, lpos, N, 1);
            }
        } else {
            int mn, mx; cin >> mn >> mx;
            if (mx < stmin[1] || mn > stmax[1]){
                cout << 0 << "\n";
                continue;
            }
            int lpos = Qrb(1, 1, N, mn);
            int rpos = Qlb(1, 1, N, mx);
            cout << rpos-lpos+1 << "\n";
        }
        /*
        for (int j = 1; j <= N; j++)
            cout << Qsum(1, 1, N, j, j) << " ";
        cout << "\n";*/
    }
}

• 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