Submission #484371

#	Time	Username	Problem	Language	Result	Execution time	Memory
484371		hoanghq2004	Growing Trees (BOI11_grow)	C++17	0 / 100	102 ms	6028 KiB

grow

#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using namespace std;

const int Nmax = 1e5 + 10;

int n, q;
int a[Nmax];

struct node {
    int minval, maxval;
    int lazy;
} st[Nmax * 4];

void push(int id, int lazy) {
    st[id].lazy += lazy;
    st[id].minval += lazy;
    st[id].maxval += lazy;
}

void add(int id, int L, int R, int u, int v, int val) {
    if (u > R || L > v) return;
    if (u <= L && R <= v) {
        push(id, val);
        return;
    }
    push(id * 2, st[id].lazy);
    push(id * 2 + 1, st[id].lazy);
    st[id].lazy = 0;
    int mid = L + R >> 1;
    add(id * 2, L, mid, u, v, val);
    add(id * 2 + 1, mid + 1, R, u, v, val);
    st[id].maxval = max(st[id * 2].maxval, st[id * 2 + 1].maxval);
    st[id].minval = min(st[id * 2].minval, st[id * 2 + 1].minval);
}

int get_prf(int id, int L, int R, int val) {
    if (st[id].maxval < val) return n + 1;
    if (L == R) return L;
    int mid = L + R >> 1;
    push(id * 2, st[id].lazy);
    push(id * 2 + 1, st[id].lazy);
    st[id].lazy = 0;
    if (st[id * 2].maxval < val) return get_prf(id * 2 + 1, mid + 1, R, val);
    else return get_prf(id * 2, L, mid, val);
}

int get_suf(int id, int L, int R, int val) {
    if (st[id].minval > val) return 0;
    if (L == R) return L;
    int mid = L + R >> 1;
    push(id * 2, st[id].lazy);
    push(id * 2 + 1, st[id].lazy);
    st[id].lazy = 0;
    if (st[id * 2 + 1].maxval <= val) return get_suf(id * 2 + 1, mid + 1, R, val);
    else return get_suf(id * 2, L, mid, val);
}

int get(int id, int L, int R, int i) {
    if (L == R) return st[id].minval;
    int mid = L + R >> 1;
    push(id * 2, st[id].lazy);
    push(id * 2 + 1, st[id].lazy);
    st[id].lazy = 0;
    if (i <= mid) return get(id * 2, L, mid, i);
    else return get(id * 2 + 1, mid + 1, R, i);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i) add(1, 1, n, i, i, a[i]);
    while (q--) {
        char type;
        cin >> type;
        if (type == 'C') {
            int L, R;
            cin >> L >> R;
            L = get_prf(1, 1, n, L);
            R = get_suf(1, 1, n, R);
            cout << R - L + 1 << '\n';
        } else {
            int c, h;
            cin >> c >> h;
            if (h > st[1].maxval) continue;
            int L = get_prf(1, 1, n, h);
            c = min(c, n - L + 1);
            int val = get(1, 1, n, L + c - 1);
            int R = get_suf(1, 1, n, val);
            int smaller = get_prf(1, 1, n, val) - 1;
            int nequal = L + c - 1 - smaller;
            add(1, 1, n, L, smaller, 1);
            add(1, 1, n, R - nequal + 1, R, 1);
        }
    }
}

Compilation message (stderr)

grow.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
grow.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
grow.cpp: In function 'void add(int, int, int, int, int, int)':
grow.cpp:33:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     int mid = L + R >> 1;
      |               ~~^~~
grow.cpp: In function 'int get_prf(int, int, int, int)':
grow.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid = L + R >> 1;
      |               ~~^~~
grow.cpp: In function 'int get_suf(int, int, int, int)':
grow.cpp:54:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     int mid = L + R >> 1;
      |               ~~^~~
grow.cpp: In function 'int get(int, int, int, int)':
grow.cpp:64:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     int mid = L + R >> 1;
      |               ~~^~~

• 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