oj.uz

답안 #537736

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537736 2022-03-15T12:44:10 Z ddy888 Growing Trees (BOI11_grow) C++17
0 / 100
 186 ms 15640 KB 
#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr<<" "<<to_string(H);debug_out(T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)

int N, M, A[100010];

struct node {
    int s,e,m,val,lazy;
    node *l, *r;
    node(int _s, int _e) {
        s = _s, e = _e, m = (s+e)/2;
        val = 0, lazy = 0;
        if (s != e) {
            l = new node(s, m);
            r = new node(m+1,e);
        }
    }
    void pushdown() {
        val += lazy;
        if (s != e) {
            l->lazy += lazy;
            r->lazy += lazy;
        }
        lazy = 0;
    }
    void add(int qs, int qe, int v) {
        if (qe < qs) return;
        if (qs == s && qe == e) lazy += v;
        else {
            if (qs > m) r->add(qs, qe, v);
            else if (qe <= m) l->add(qs, qe, v);
            else l->add(qs, m, v), r->add(m+1, qe, v);
            l->pushdown(), r->pushdown();
            val = max(l->val, r->val);
        }
    }
    int find(int v) { // index of first element >= v
        if (s == e) return s;
        if (val < v) return r->find(v);
        if (l->val >= v) return l->find(v);
        return r->find(v);
    }
    int get(int qs, int qe) {
        pushdown();
        if (qs <= s && qe >= e) return val;
        if (qs > m) return r->get(qs, qe);
        if (qe <= m) return l->get(qs, qe);
        return max(l->get(qs, m), r->get(m + 1, qe));
    }
} *seg;

signed main() {
    fast;
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) cin >> A[i];
    sort(A + 1, A + 1 + N);
    seg = new node(1, N);
    for (int i = 1; i <= N; ++i) seg->add(i, i, A[i]);
    while (M--) {
        char op; int a, b; cin >> op >> a >> b;
        if (op == 'F') {
            int st = seg->find(b);
            int high = seg->get(min(N, st + a - 1), min(N, st + a - 1));
            int mid = seg->find(high);
            int en = seg->find(high + 1);
            if (mid > st) --mid;
            if (seg->get(en, en) > high) --en;
            int rem = a - (mid - st + 1);
            seg->add(st, mid, 1);
            seg->add(max(mid + 1, en - rem + 1), en, 1);
        } else {
            int lx = seg->find(a);
            int rx = seg->find(b + 1);
            if (seg->get(lx, lx) < a) {cout << 0 << '\n'; continue;}
            if (seg->get(rx, rx) > b) --rx;
            cout << rx - lx + 1 << '\n';
        }
        // for (int i = 1; i <= N; ++i) cout << seg->get(i, i) << ' ';
        // cout << '\n';
    }
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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