Submission #537736

#	Time	Username	Problem	Language	Result	Execution time	Memory
537736		ddy888	Growing Trees (BOI11_grow)	C++17	0 / 100	186 ms	15640 KiB

grow

#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
• 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