oj.uz

Submission #868579

# Submission time Handle Problem Language Result Execution time Memory
868579 2023-10-31T22:08:25 Z Karoot Growing Trees (BOI11_grow) C++17
100 / 100
 160 ms 13876 KB 
#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
 
#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()
 
using namespace std;
 
typedef long long ll;
 
ll linf = 1e15+1;
 
inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}
 
struct Node {
    int x;
    int y;
    int lzAdd;
};
 
const int MAXN = 8e5+7;
 
Node ST[MAXN];
int leftOf[MAXN], rightOf[MAXN];
vector<int> vals;
 
void buildTree(int l, int r, int node = 1){
    leftOf[node] = l;
    rightOf[node] = r;
    if (l == r){
        ST[node].x = vals[l];
        ST[node].y = vals[r];
        ST[node].lzAdd = 0;
        return;
    }
    int mid = (l+r)/2;
    buildTree(l, mid, 2*node);
    buildTree(mid+1, r, 2*node+1);
    ST[node].x = ST[2*node].x;
    ST[node].y = ST[2*node+1].y;
    ST[node].lzAdd = 0;
    return;
}
 
void pushdown(int node){
    int a = 2*node, b = 2*node+1;
    ST[a].x += ST[node].lzAdd;
    ST[a].y += ST[node].lzAdd;
    ST[b].x += ST[node].lzAdd;
    ST[b].y += ST[node].lzAdd;
    ST[b].lzAdd += ST[node].lzAdd;
    ST[a].lzAdd += ST[node].lzAdd;
    if (leftOf[a] == rightOf[a])ST[a].lzAdd = 0;
    if (leftOf[b] == rightOf[b])ST[b].lzAdd = 0;
    ST[node].lzAdd = 0;
}
 
void update(int l, int r, int node = 1){
    if (leftOf[node] == l && rightOf[node] == r){
        ST[node].lzAdd++;
        if (leftOf[node] == rightOf[node])ST[node].lzAdd = 0;
        ST[node].x++;
        ST[node].y++;
        return;
    }
    int a = 2*node, b = 2*node+1;
    pushdown(node);
    if (r <= rightOf[a]){
        update(l, r, a);
    } else if (l >= leftOf[b]){
        update(l, r, b);
    } else {
        update(l, rightOf[a], a);
        update(leftOf[b], r, b);
    }
    ST[node].x = ST[a].x;
    ST[node].y = ST[b].y;
    return;
}
 
int findLC(int l, int r, int val, int node = 1){
    if (l == r){
        return l;
    }
    int a = 2*node, b = 2*node+1;
    pushdown(node);
    if (val <= ST[a].y){
        return findLC(l, rightOf[a], val, a);
    } else {
        return findLC(leftOf[b], r, val, b);
    }
}
 
int findRC(int l, int r, int val, int node = 1){
    if (l == r){
        return l;
    }
    int a = 2*node, b = 2*node+1;
    pushdown(node);
    if (val >= ST[b].x){
        return findRC(leftOf[b], r, val, b);
    } else {
        return findRC(l, rightOf[a], val, a);
    }
}
 
int fetchIndex(int x, int node = 1){
    if (leftOf[node] == rightOf[node]){
        return ST[node].x;
    }
    int a = 2*node, b = 2*node+1;
    pushdown(node);
    if (x <= rightOf[a]){
        return fetchIndex(x, a);
    } else {
        return fetchIndex(x, b);
    }
}
 
int main(){
    scoobydoobydoo();
    int n, q; cin >> n >> q;
    for (int i = 0; i < n; i++){
        int t; cin >> t;
        vals.push_back(t);
    }
 
    sort(all(vals));
 
    buildTree(0, n-1);
 
    vector<ll> ans;
 
    while (q--){
        char c; cin >> c;
        if (c == 'F'){
            int ci, h; cin >> ci >> h;
            int Lc = findLC(0, n-1, h);
            int orWorth = fetchIndex(Lc);
            if (Lc == n-1 && orWorth < h)continue;
            //cout << "Lc: " << Lc << endl;
            if (Lc + ci - 1 < n){
                int x = fetchIndex(Lc + ci - 1);
                int Rx = findRC(0, n-1, x);
                int Lx = findLC(0, n-1, x);
                if (x == orWorth){
                    update(Rx-ci+1, Rx);
                    //cout << "x == orWorth" << endl;
                    continue;
                }
                //cout << x << " " << Rx << " " << Lx << endl;
                update(Lc, Lx-1);
                update(Rx-ci+Lx-Lc+1, Rx);
            } else {
                update(Lc, n-1);
            }
        } else {
            int mi, ma; cin >> mi >> ma;
            int Rmax = findRC(0, n-1, ma);
            int Lmi = findLC(0, n-1, mi);
            //cout << Rmax << " " << Lmi << endl;
 
            if (Lmi > Rmax || ma < ST[1].x || mi > ST[1].y){
                ans.push_back(0);
            } else {
                ans.push_back(Rmax-Lmi+1);
            }
 
            //cout << Rmax - Lmi + 1 << endl;
        }
        /*
        for (int i = 1; i <= 9; i++){
            cout << i << ": " << ST[i].x << " " << ST[i].y << ": " << ST[i].lzAdd << endl;
        }
        */
    }
 
    for (auto& e : ans){
        cout << e << endl;
    }
 
 
 
 
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 12756 KB Output is correct
2 Correct 145 ms 12808 KB Output is correct
3 Correct 90 ms 12252 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 5 ms 4700 KB Output is correct
3 Correct 6 ms 4708 KB Output is correct
4 Correct 4 ms 4668 KB Output is correct
5 Correct 130 ms 8452 KB Output is correct
6 Correct 139 ms 8680 KB Output is correct
7 Correct 7 ms 6744 KB Output is correct
8 Correct 102 ms 8212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 8676 KB Output is correct
2 Correct 133 ms 8944 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 114 ms 8184 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 8684 KB Output is correct
2 Correct 142 ms 8516 KB Output is correct
3 Correct 9 ms 6740 KB Output is correct
4 Correct 127 ms 8568 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 10320 KB Output is correct
2 Correct 148 ms 12496 KB Output is correct
3 Correct 31 ms 9564 KB Output is correct
4 Correct 71 ms 12292 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 12524 KB Output is correct
2 Correct 141 ms 12632 KB Output is correct
3 Correct 96 ms 12496 KB Output is correct
4 Correct 31 ms 9560 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 12496 KB Output is correct
2 Correct 105 ms 12748 KB Output is correct
3 Correct 93 ms 12492 KB Output is correct
4 Correct 30 ms 9564 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 12996 KB Output is correct
2 Correct 142 ms 12500 KB Output is correct
3 Correct 28 ms 11740 KB Output is correct
4 Correct 110 ms 12888 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 12632 KB Output is correct
2 Correct 145 ms 12896 KB Output is correct
3 Correct 151 ms 12500 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 13876 KB Output is correct