oj.uz

Submission #996258

# Submission time Handle Problem Language Result Execution time Memory
996258 2024-06-10T10:06:26 Z Icelast Growing Trees (BOI11_grow) C++17
100 / 100
 175 ms 5720 KB 
#include <iostream>
#include <bits/stdc++.h>
#define ll int
using namespace std;
const ll maxn = 2*1e5+5, INF = 2e9+9;
struct SegmentTree{
    struct Node{
        int sum, lz, mx;
    };
    int n, N;
    vector<Node> T;
    SegmentTree(int n) : n(n){
        N = 1;
        while(N < n) N*=2;
        T.resize(N*2+1, {0, 0, -INF});
    };
    void merge(Node &n, Node a, Node b){
        n.sum = a.sum+b.sum;
        n.mx = max(a.mx, b.mx);
    }
    void upd(int i, ll x){
        auto upd = [&](auto upd, int node, int low, int high, int i, ll x) -> void{
            if(low == high){
                T[node].sum = x;
                T[node].mx = x;
                return;
            }
            int mid = (low+high)/2;
            if(i <= mid){
                upd(upd, node*2, low, mid, i, x);
            }else{
                upd(upd, node*2+1, mid+1, high, i, x);
            }
            merge(T[node], T[node*2], T[node*2+1]);
        };
        upd(upd, 1, 1, N, i, x);
    }
    void down(int node, int low, int high){
        int len = high-low+1;
        for(int child = node*2; child <= node*2+1; child++){
            if(child >= 2*N) continue;
            T[child].lz += T[node].lz;
        }
        T[node].sum += T[node].lz*len;
        T[node].mx += T[node].lz;
        T[node].lz = 0;
    }
    void updRange(int l, int r, ll x){
        if(l > r) return;
        auto updRange = [&](auto updRange, int node, int low, int high, int l, int r, ll x) -> void{
            down(node, low, high);
            if(low > r || l > high) return;
            if(low >= l && r >= high){
                T[node].lz += x;
                down(node, low, high);
                return;
            }
            int mid = (low+high)/2;
            updRange(updRange, node*2, low, mid, l, r, x);
            updRange(updRange, node*2+1, mid+1, high, l, r, x);
            merge(T[node], T[node*2], T[node*2+1]);
        };
        updRange(updRange, 1, 1, N, l, r, x);
    }
    int walkMax(int l, int r, int dir, ll x){
        auto walkMax = [&](auto walkMax, int node, int low, int high, int l, int r, int dir, ll x) -> int{
            if(low > r || l > high){
                return -1;
            }
            down(node, low, high);
            if(T[node].mx < x){
                return -1;
            }
            if(low == high) return low;
            int mid = (low+high)/2;
            int left = walkMax(walkMax, node*2, low, mid, l, r, dir, x);
            if(left != -1) return left;
            return walkMax(walkMax, node*2+1, mid+1, high, l, r, dir, x);
        };
        return walkMax(walkMax, 1, 1, N, l, r, dir, x);
    }
    ll getSum(int l, int r){
        if(l > r) return 0;
        auto getSum = [&](auto getSum, int node, int low, int high, int l, int r) -> ll{
            if(low > r || l > high) return 0;
            if(low >= l && r >= high){
                down(node, low, high);
                return T[node].sum;
            }
            down(node, low, high);
            int mid = (low+high)/2;
            return getSum(getSum, node*2, low, mid, l, r)+getSum(getSum, node*2+1, mid+1, high, l, r);
        };
        return getSum(getSum, 1, 1, N, l, r);
    }
};
void solve(){
    int n, Q;
    cin >> n >> Q;
    vector<ll> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a.begin()+1, a.end());
    SegmentTree T(n+1);
    for(int i = 1; i <= n; i++){
        T.upd(i, a[i]);
    }

    for(int i = 1; i <= Q; i++){
        char t;
        ll c, h, low, high;
        cin >> t;
        if(t == 'F'){
            cin >> c >> h;
            int l = T.walkMax(1, n, 0, h);
            if(l == -1) continue;
            int r = l+c-1;
            r = min(r, n);
            ll x = T.getSum(r, r);
            int down = T.walkMax(1, n, 0, x);
            int up = T.walkMax(1, n, 0, x+1)-1;
            int len = r-down+1;
            if(up == -2) up = n;
            T.updRange(l, down-1, 1);
            T.updRange(up-len+1, up, 1);
        }else{
            cin >> low >> high;
            int l = T.walkMax(1, n, 0, low);
            int r = T.walkMax(1, n, 0, high+1)-1;
            if(r == -2) r = n;
            if(l == -1) l = n+1;
            ll res = r-l+1;
            cout << res << "\n";
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 3920 KB Output is correct
2 Correct 121 ms 5460 KB Output is correct
3 Correct 114 ms 5460 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 37 ms 1620 KB Output is correct
6 Correct 42 ms 1872 KB Output is correct
7 Correct 5 ms 600 KB Output is correct
8 Correct 20 ms 1372 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 860 KB Output is correct
2 Correct 44 ms 1872 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 26 ms 1620 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1072 KB Output is correct
2 Correct 50 ms 840 KB Output is correct
3 Correct 10 ms 600 KB Output is correct
4 Correct 59 ms 1868 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 2388 KB Output is correct
2 Correct 102 ms 5204 KB Output is correct
3 Correct 16 ms 2136 KB Output is correct
4 Correct 79 ms 5204 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 3920 KB Output is correct
2 Correct 101 ms 5204 KB Output is correct
3 Correct 115 ms 5336 KB Output is correct
4 Correct 13 ms 1624 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 3900 KB Output is correct
2 Correct 69 ms 5100 KB Output is correct
3 Correct 116 ms 5456 KB Output is correct
4 Correct 13 ms 1624 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 3920 KB Output is correct
2 Correct 110 ms 4944 KB Output is correct
3 Correct 30 ms 4440 KB Output is correct
4 Correct 71 ms 5048 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 3924 KB Output is correct
2 Correct 105 ms 5440 KB Output is correct
3 Correct 175 ms 5720 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 4432 KB Output is correct