Submission #949339

#	Time	Username	Problem	Language	Result	Execution time	Memory
949339		Esgeer	Growing Trees (BOI11_grow)	C++17	0 / 100	76 ms	10400 KiB

grow

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <unistd.h>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define vb vector<bool>
#define vvb vector<vb>
#define endl '\n'
#define sp << " " <<
#define F(i, s, n) for(int i = s; i < n; i++)
#define pb push_back
#define fi first
#define se second

int mod = 1e9+7;
int inf = 1e16;
const int N = 2e5+5;

int t[4*N];
int lazy[4*N];
int a[N];

void push(int node, int l, int r) {
    if(lazy[node] == 0) return;
    t[node] += lazy[node];
    if(l != r) {
        lazy[node*2+1] += lazy[node];
        lazy[node*2+2] += lazy[node];
    }
    lazy[node] = 0;
}
void build(int node, int l, int r) {
    if(l == r) {
        t[node] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(node*2+1, l, mid);
    build(node*2+2, mid+1, r);
    t[node] = max(t[node*2+1], t[node*2+2]);
}
void update(int node, int l, int r, int L, int R) {
    push(node, l, r);
    if(l > R || r < L) return;
    if(l >= L && r <= R) {
        lazy[node]++;
        push(node, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    update(node*2+1, l, mid, L, R);
    update(node*2+2, mid+1, r, L, R);
    t[node] = max(t[node*2+1], t[node*2+2]);
}
int lb(int node, int l, int r, int val) {
    push(node, l, r);
    if(l == r) {
        if(t[node] >= val) return l;
        else return l+1;
    }
    int mid = (l + r) >> 1;
    if(t[node*2+1] >= val) return lb(node*2+1, l, mid, val);
    else return lb(node*2+2, mid+1, r, val);
}
int query(int node, int l, int r, int idx) {
    push(node, l, r);
    if(l > idx || r < idx) return 0;
    if(l == r) {
        return t[node];
    }
    int mid = (l + r) >> 1;
    return max(query(node*2+1, l, mid, idx), query(node*2+2, mid+1, r, idx));
}

void solve() {
    int n, q;
    cin >> n >> q;
    F(i, 0, n) cin >> a[i];
    sort(a, a+n);
    build(0, 0, n-1);
    F(i, 0, q) {
        char type;
        cin >> type;
        if(type == 'C') {
            int l, r;
            cin >> l >> r;
            cout << lb(0, 0, n-1, r+1) - lb(0, 0, n-1, l) << endl;
        } else {
            int c, h;
            cin >> c >> h;
            int idx = lb(0, 0, n-1, h);
            int value = query(0, 0, n-1, idx+c-1);
            int idx2 = lb(0, 0, n-1, value);
            int idx3 = lb(0, 0, n-1, value+1) - 1;
            if(idx2-1 >= idx) update(0, 0, n-1, idx, idx2-1);
            update(0, 0, n-1, idx3 - (c - idx2 + idx - 1), idx3);
        }
    }
}
 
void setIO() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Local
        freopen("local.in", "r", stdin);
        freopen("local.out", "w", stdout);
    #else 
        // freopen("poetry.in","r",stdin);
        // freopen("poetry.out","w",stdout);
    #endif
}
signed main() {
    setIO();
    int t = 1;
    //cin >> t;
    while(t--) solve();
}

• 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