oj.uz

Submission #867423

# Submission time Handle Problem Language Result Execution time Memory
867423 2023-10-28T11:11:51 Z TahirAliyev Growing Trees (BOI11_grow) C++17
0 / 100
 199 ms 5720 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){
    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;
        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;
        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;
            update(1, 1, n + 1, ul1, ur1);
            int ur2 = upb(a) - 1;
            int ul2 = ur2 - (k - (ur1 - ul1 + 1)) + 1;
            update(1, 1, n + 1, ul2, ur2);
        }
        else{
            int a, b; cin >> a >> b;
            cout << upb(b) - lowb(a) << '\n';
        }
    }        
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 4552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 149 ms 3664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 3656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 4056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 4296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 4400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 5160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 4812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 197 ms 5720 KB Output isn't correct
2 Halted 0 ms 0 KB -