제출 #996230

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
996230		Icelast	Growing Trees (BOI11_grow)	C++17	0 / 100	95 ms	5968 KiB

grow

#include <iostream>
#include <bits/stdc++.h>
#define ll int
using namespace std;
const ll maxn = 2*1e5+5, INF = 1e9+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{
            if(low > r || l > high) return;
            if(low >= l && r >= high){
                T[node].lz += x;
                down(node, low, high);
                return;
            }
            down(node, low, high);
            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: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10