제출 #1133908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133908		anarch_y	Growing Trees (BOI11_grow)	C++20	100 / 100	110 ms	3772 KiB

grow

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

struct Node{
    int val, lzAdd;
};

struct LazySegmentTree{
    int none = 0;
    Node def = {0, none};
    vector<Node> tree;
    int len;

    LazySegmentTree(int N, vector<int> &A){
        int p = ceil(log2(N));
        len = (1<<p);
        tree.resize(2*len, def);
        for(int i=0; i<N; i++){
            tree[i+len] = {A[i], none};
        }
    }

    void pushup(int k){
	    tree[k].val = max(tree[2*k].val, tree[2*k+1].val);
    }

    void pushdown(int k, int x, int y){
        if(tree[k].lzAdd != none){
            int v = tree[k].lzAdd;
            tree[2*k].lzAdd += v;
            tree[2*k+1].lzAdd += v;
            tree[2*k].val += v;
            tree[2*k+1].val += v;
            tree[k].lzAdd = none;
        }
    }

    void build(int k, int x, int y){
        if(x == y) return;
        int d = (x+y)/2; 
        build(2*k, x, d);
        build(2*k+1, d+1, y);
        pushup(k);
    }
 
    void begin(){
        build(1, 0, len-1);
    }

    void add(int a, int b, int v, int k, int x, int y){
        if(b < x or a > y) return;
        if(a <= x and y <= b){
            tree[k].val += v;
            tree[k].lzAdd += v;
            return;
        }
        pushdown(k, x, y);
        int d = (x+y)/2;
        add(a, b, v, 2*k, x, d);
        add(a, b, v, 2*k+1, d+1, y);
        pushup(k);
    }

    void add(int a, int b, int v){
        add(a, b, v, 1, 0, len-1);
    }

    int query(int a, int b, int k, int x, int y){
        if(b < x or a > y) return 0;
        if(a <= x and y <= b) return tree[k].val;
        int d = (x+y)/2;
        pushdown(k, x, y);
        int s1 = query(a, b, 2*k, x, d);
        int s2 = query(a, b, 2*k+1, d+1, y);
        return max(s1, s2);
    }
    
    int query(int a, int b){
        return query(a, b, 1, 0, len-1);
    }

    int find(int v, int k, int x, int y){
        if(tree[k].val < v) return -1;
        if(x == y) return x;
        pushdown(k, x, y);
        int d = (x+y)/2;
        int res = find(v, 2*k, x, d);
        if(res == -1){
            res = find(v, 2*k+1, d+1, y);
        }
        return res;
    }

    int find(int v){
        return find(v, 1, 0, len-1);
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    vector<int> v;
    for(int i=0; i<n; i++){
        int x; cin >> x;
        v.pb(x);
    }
    sort(all(v));
    vector<int> A(n+1);
    for(int i=1; i<=n; i++){
        A[i] = v[i-1];
    }
    LazySegmentTree lseg(n+1, A);
    lseg.begin();
    while(m--){
        char ch; cin >> ch;
        if(ch == 'F'){
            int c, h; cin >> c >> h;
            if(h == 0) h = 1;
            int i = lseg.find(h);
            if(i == -1) continue;
            int j = min(i+c-1, n);
            int mx = lseg.query(i, j);
            int k1 = lseg.find(mx);
            int k2 = lseg.find(mx+1);
            if(k2 == -1) k2 = n;
            else k2--;
            if(i >= k1){
                int l = j-i+1;
                lseg.add(k2-l+1, k2, 1);
            }
            else{
                lseg.add(i, k1-1, 1);
                int l = j-k1+1;
                lseg.add(k2-l+1, k2, 1);
            }
        }
        else{
            int a, b; cin >> a >> b;
            int i = lseg.find(a);
            if(i == -1){
                cout << 0 << "\n";
                continue;
            }
            int j = lseg.find(b+1);
            if(j == -1) j = n;
            else j--;
            cout << j-i+1 << "\n";
        }
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10