oj.uz

답안 #782450

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
782450 2023-07-14T01:58:29 Z hgmhc Growing Trees (BOI11_grow) C++17
100 / 100
 599 ms 7596 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 200 ms 5956 KB Output is correct
2 Correct 338 ms 7520 KB Output is correct
3 Correct 453 ms 7468 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5460 KB Output is correct
2 Correct 4 ms 5460 KB Output is correct
3 Correct 5 ms 5460 KB Output is correct
4 Correct 5 ms 5460 KB Output is correct
5 Correct 62 ms 6484 KB Output is correct
6 Correct 72 ms 6700 KB Output is correct
7 Correct 17 ms 5460 KB Output is correct
8 Correct 49 ms 6148 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 5828 KB Output is correct
2 Correct 75 ms 6840 KB Output is correct
3 Correct 5 ms 5460 KB Output is correct
4 Correct 48 ms 6292 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 5788 KB Output is correct
2 Correct 81 ms 6692 KB Output is correct
3 Correct 38 ms 5576 KB Output is correct
4 Correct 69 ms 6840 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 197 ms 5840 KB Output is correct
2 Correct 289 ms 7104 KB Output is correct
3 Correct 15 ms 5844 KB Output is correct
4 Correct 366 ms 7108 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 5860 KB Output is correct
2 Correct 262 ms 7184 KB Output is correct
3 Correct 451 ms 7376 KB Output is correct
4 Correct 15 ms 5844 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 215 ms 5948 KB Output is correct
2 Correct 188 ms 7088 KB Output is correct
3 Correct 458 ms 7460 KB Output is correct
4 Correct 15 ms 5864 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 323 ms 5928 KB Output is correct
2 Correct 264 ms 5836 KB Output is correct
3 Correct 56 ms 6540 KB Output is correct
4 Correct 236 ms 6976 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 228 ms 6056 KB Output is correct
2 Correct 269 ms 7392 KB Output is correct
3 Correct 599 ms 7596 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 6240 KB Output is correct