oj.uz

Submission #466380

# Submission time Handle Problem Language Result Execution time Memory
466380 2021-08-19T06:40:04 Z jli12345 Growing Trees (BOI11_grow) C++14
100 / 100
 281 ms 11204 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 10240 KB Output is correct
2 Correct 202 ms 10580 KB Output is correct
3 Correct 87 ms 10564 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 3 ms 464 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 53 ms 1872 KB Output is correct
6 Correct 81 ms 2060 KB Output is correct
7 Correct 7 ms 968 KB Output is correct
8 Correct 30 ms 1612 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 2116 KB Output is correct
2 Correct 71 ms 2232 KB Output is correct
3 Correct 5 ms 868 KB Output is correct
4 Correct 48 ms 1784 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2368 KB Output is correct
2 Correct 71 ms 2116 KB Output is correct
3 Correct 15 ms 972 KB Output is correct
4 Correct 67 ms 2360 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 5756 KB Output is correct
2 Correct 174 ms 10232 KB Output is correct
3 Correct 24 ms 2864 KB Output is correct
4 Correct 71 ms 10412 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 9900 KB Output is correct
2 Correct 182 ms 10228 KB Output is correct
3 Correct 100 ms 10432 KB Output is correct
4 Correct 23 ms 2828 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 10036 KB Output is correct
2 Correct 144 ms 10248 KB Output is correct
3 Correct 85 ms 10596 KB Output is correct
4 Correct 23 ms 2844 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 10632 KB Output is correct
2 Correct 191 ms 10096 KB Output is correct
3 Correct 74 ms 9540 KB Output is correct
4 Correct 120 ms 9968 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 10324 KB Output is correct
2 Correct 192 ms 10536 KB Output is correct
3 Correct 281 ms 10768 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 11204 KB Output is correct