제출 #782450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
782450		hgmhc	Growing Trees (BOI11_grow)	C++17	100 / 100	599 ms	7596 KiB

grow

#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x),end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x=max(x,y)
#define mup(x,y) x=min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
using ii = pair<int,int>;
using ll = long long;

const int INF = 1e9;

template <const int N = 1<<17>
struct lazy {
    struct node { ll sum; int right; };
    node merge(node x, node y){ return {x.sum+y.sum,y.right}; }
    node v[2*N]{}; int z[2*N]{};
    lazy(int *f, int *l) {
        rep(i,f,l-1) v[N+i-f] = {*i,*i};
        rep(i,l-f,N-1) v[N+i] = {INF,INF};
        per(i,1,N-1) v[i] = merge(v[2*i],v[2*i+1]);
    }
    void prop(int k, int s, int e) {
        v[k].sum += z[k]*ll(e-s+1);
        v[k].right += z[k];
        if (s != e) {
            z[2*k] += z[k];
            z[2*k+1] += z[k];
        }
        z[k] = 0;
    }
    void update(int a, int b, int k = 1, int s = 0, int e = N-1) {
        prop(k,s,e);
        if (a <= s and e <= b) { z[k]++, prop(k,s,e); return; }
        if (b < s or e < a) return;
        int m = (s+e)/2;
        update(a,b,2*k,s,m), update(a,b,2*k+1,m+1,e);
        v[k] = merge(v[2*k],v[2*k+1]);
    }
    ll query(int a, int b, int k = 1, int s = 0, int e = N-1) {
        prop(k,s,e);
        if (a <= s and e <= b) return v[k].sum;
        if (b < s or e < a) return v[0].sum;
        int m = (s+e)/2;
        return query(a,b,2*k,s,m) + query(a,b,2*k+1,m+1,e);
    }
    int lb(int x, int k = 1, int s = 0, int e = N-1) {
        int m;
        prop(k,s,e);
        while (s < e) {
            m = (s+e)/2;
            prop(2*k,s,m), prop(2*k+1,m+1,e);
            if (x <= v[2*k].right) k = 2*k, e = m;
            else k = 2*k+1, s = m+1;
        }
        if (x <= v[k].right) return s;
        else return s+1;
    }
};

const int N = 1e5+3, M = N;
int n, m, a[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    rep(i,1,n) cin >> a[i];
    a[0] = -1;
    sort(a+1,a+n+1);
    lazy seg(a,a+n+1);
    rep(i,1,m) {
        char c; int x, y; cin >> c >> x >> y;
        if (c == 'F') {
            // 높이가 y 이상인 가장 작은 나무 x개
            int f1 = seg.lb(y);
            if (f1 > n) continue;
            int s = y, e = INF, m;
            while (s <= e) {
                m = (s+e)/2;
                if (min(n+1,seg.lb(m+1))-f1 <= x) s = m+1;
                else e = m-1;
            }
            // [y,e]에 속한 나무의 개수가 x 이하인 최대의 e
            int l1 = min(n,seg.lb(e+1)-1); // [y,e]의 나무들에 1씩 더함
            int l2, f2;
            if (f1 <= l1) {
                seg.update(f1,l1);
                l2 = min(n,seg.lb(s+1)-1); // s의 나무들 중 뒷쪽부터 1씩 더할 예정
                f2 = max(l1+1,l2-(x-(l1-f1+1))+1);
            } else {
                l2 = min(n,seg.lb(s+1)-1); // s의 나무들 중 뒷쪽부터 1씩 더할 예정
                f2 = max(f1,l2-x+1);
            } 
            if (f2 <= l2) seg.update(f2,l2);
        } else {
            cout << min(n+1,seg.lb(y+1))-min(n+1,seg.lb(x)) << '\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