oj.uz

답안 #780663

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
780663 2023-07-12T11:34:15 Z hgmhc Growing Trees (BOI11_grow) C++17
0 / 100
 231 ms 8116 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 left, right; };
    node merge(node x, node y){ return {x.sum+y.sum,x.left,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,*i};
        rep(i,l-f,N-1) v[N+i] = {INF,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].left += z[k], 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-1;
            else k = 2*k+1, s = m+1;
        }
        if (x <= v[k].left) 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];
    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);
            int s = y, e = INF, m;
            while (s <= e) {
                m = (s+e)/2;
                if (seg.lb(m+1)-f1 < x) s = m+1;
                else e = m-1;
            }
            // [y,e]에 속한 나무의 개수가 x 미만인 최대의 e
            int l1 = seg.lb(e+1)-1; // [y,e]의 나무들에 1씩 더함
            seg.update(f1,min(n,l1));
            if (l1 > n) continue;
            int l2 = seg.lb(s+1)-1; // s의 나무들 중 뒷쪽부터 1씩 더할 예정
            int f2 = l1-f1+l2-x+2; // [f2,l2] l2-f2+1=x-(l1-f1+1) -> l1-f1+l2-x+2=f2
            seg.update(f2,l2);
        } else {
            // 높이가 [x,y]에 포함되는 나무의 수
            cout << seg.lb(y+1)-seg.lb(x) << '\n';
        }
    }
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 137 ms 6944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 58 ms 6528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 58 ms 6748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 167 ms 6724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 170 ms 6756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 167 ms 6980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 231 ms 7524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 174 ms 7196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 66 ms 8116 KB Output isn't correct
2 Halted 0 ms 0 KB -