oj.uz

Submission #867439

# Submission time Handle Problem Language Result Execution time Memory
867439 2023-10-28T11:49:44 Z TahirAliyev Growing Trees (BOI11_grow) C++17
100 / 100
 210 ms 5196 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pii pair<int, int>
#define oo 2e9

const int MAX = 1e5 + 5;
int n, q;
int tree[4 * MAX], lazy[4 * MAX];
vector<int> v;

void build(int node = 1, int l = 1, int r = n + 1){
    if(l == r){
        tree[node] = v[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}

void relax(int node, int l, int r){
    if(!lazy[node]) return;
    tree[node] += lazy[node];
    if(l == r){
        lazy[node] = 0;
        return;
    }
    lazy[2 * node] += lazy[node];
    lazy[2 * node + 1] += lazy[node];
    lazy[node] = 0;
}

void update(int node, int l, int r, int ul, int ur){
    relax(node, l, r);
    if(ur < l || r < ul) return;
    if(ul <= l && r <= ur){
        lazy[node]++;
        relax(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(2 * node, l, mid, ul, ur);
    update(2 * node + 1, mid + 1, r, ul, ur);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}

int get(int node, int l, int r, int pos){
    relax(node, l, r);
    if(l == r) return tree[node];
    int mid = (l + r) / 2;
    if(pos <= mid){
        return get(2 * node, l, mid, pos);
    }
    else{
        return get(2 * node + 1, mid + 1, r, pos);
    }
}

int lowb(int a){
    int node = 1;
    int l = 1, r = n + 1;
    while(l < r){
        int mid = (l + r) / 2;
        relax(node, l, r);
        relax(2 * node, l, mid);
        relax(2 * node + 1, mid + 1, r);
        if(tree[2 * node] >= a){
            node *= 2;
            r = mid;
        }
        else{
            node = 2 * node + 1;
            l = mid + 1;
        }
    }
    return l;
}

int upb(int a){
    int node = 1;
    int l = 1, r = n + 1;
    while(l < r){
        int mid = (l + r) / 2;
        relax(node, l, r);
        relax(2 * node, l, mid);
        relax(2 * node + 1, mid + 1, r);
        if(tree[2 * node] > a){
            node *= 2;
            r = mid;
        }
        else{
            node = 2 * node + 1;
            l = mid + 1;
        }
    }
    return l;
}

int main(){
    cin >> n >> q;
    v.push_back(0);
    for(int i = 1; i <= n; i++){
        int a; cin >> a;
        v.push_back(a);
    }
    sort(v.begin(), v.end());
    v.push_back(oo);
    build();
    while(q--){
        string s; cin >> s;
        if(s[0] == 'F'){
            int k, s; cin >> k >> s;
            int ul1 = lowb(s);
            if(ul1 + k - 1 > n){
                update(1, 1, n + 1, ul1, n);
                continue;
            }
            int a = get(1, 1, n + 1, ul1 + k - 1);
            int ur1 = lowb(a) - 1;
            int ur2 = upb(a) - 1;
            int ul2 = ur2 - (k - (ur1 - ul1 + 1)) + 1;
            update(1, 1, n + 1, ul1, ur1);
            update(1, 1, n + 1, ul2, ur2);
        }
        else{
            int a, b; cin >> a >> b;
            cout << upb(b) - lowb(a) << '\n';
        }
    }        
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 3876 KB Output is correct
2 Correct 193 ms 5068 KB Output is correct
3 Correct 137 ms 5000 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2396 KB Output is correct
2 Correct 7 ms 2408 KB Output is correct
3 Correct 7 ms 2396 KB Output is correct
4 Correct 5 ms 2392 KB Output is correct
5 Correct 144 ms 3880 KB Output is correct
6 Correct 176 ms 3896 KB Output is correct
7 Correct 8 ms 2904 KB Output is correct
8 Correct 147 ms 3152 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 2900 KB Output is correct
2 Correct 168 ms 3796 KB Output is correct
3 Correct 3 ms 2392 KB Output is correct
4 Correct 156 ms 3304 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 2944 KB Output is correct
2 Correct 177 ms 3948 KB Output is correct
3 Correct 11 ms 2652 KB Output is correct
4 Correct 166 ms 3992 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 3096 KB Output is correct
2 Correct 167 ms 4844 KB Output is correct
3 Correct 41 ms 3116 KB Output is correct
4 Correct 106 ms 4824 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 3480 KB Output is correct
2 Correct 168 ms 4916 KB Output is correct
3 Correct 132 ms 5072 KB Output is correct
4 Correct 40 ms 3164 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 3528 KB Output is correct
2 Correct 139 ms 4868 KB Output is correct
3 Correct 134 ms 5060 KB Output is correct
4 Correct 44 ms 3412 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 3592 KB Output is correct
2 Correct 165 ms 4804 KB Output is correct
3 Correct 43 ms 4044 KB Output is correct
4 Correct 143 ms 4684 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 3532 KB Output is correct
2 Correct 183 ms 5192 KB Output is correct
3 Correct 176 ms 5196 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 4044 KB Output is correct