oj.uz

Submission #484375

# Submission time Handle Problem Language Result Execution time Memory
484375 2021-11-03T04:35:38 Z hoanghq2004 Growing Trees (BOI11_grow) C++14
100 / 100
 165 ms 5624 KB 
#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);
}

// vi tri dau tien <= x

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].minval <= 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() {
//    freopen("test.inp", "r", stdin);
    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;
            int _L = L, _R = R;
            L = get_prf(1, 1, n, L);
            R = get_prf(1, 1, n, R + 1);
            cout << R - L << '\n';
        } else {
            int c, h;
            cin >> c >> h;
            if (h > st[1].maxval) continue;
            int L = get_prf(1, 1, n, h);
            assert(get(1, 1, n, L) >= 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

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:56:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |     int mid = L + R >> 1;
      |               ~~^~~
grow.cpp: In function 'int get(int, int, int, int)':
grow.cpp:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |     int mid = L + R >> 1;
      |               ~~^~~
grow.cpp: In function 'int main()':
grow.cpp:87:17: warning: unused variable '_L' [-Wunused-variable]
   87 |             int _L = L, _R = R;
      |                 ^~
grow.cpp:87:25: warning: unused variable '_R' [-Wunused-variable]
   87 |             int _L = L, _R = R;
      |                         ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 3904 KB Output is correct
2 Correct 117 ms 5400 KB Output is correct
3 Correct 108 ms 5312 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 41 ms 1604 KB Output is correct
6 Correct 43 ms 1736 KB Output is correct
7 Correct 5 ms 588 KB Output is correct
8 Correct 23 ms 1296 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 800 KB Output is correct
2 Correct 44 ms 1864 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 28 ms 1480 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 964 KB Output is correct
2 Correct 49 ms 1860 KB Output is correct
3 Correct 10 ms 588 KB Output is correct
4 Correct 46 ms 1884 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 2176 KB Output is correct
2 Correct 106 ms 5060 KB Output is correct
3 Correct 16 ms 1532 KB Output is correct
4 Correct 88 ms 5176 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 3684 KB Output is correct
2 Correct 107 ms 5132 KB Output is correct
3 Correct 103 ms 5304 KB Output is correct
4 Correct 16 ms 1492 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 3908 KB Output is correct
2 Correct 79 ms 5060 KB Output is correct
3 Correct 107 ms 5316 KB Output is correct
4 Correct 15 ms 1484 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 3884 KB Output is correct
2 Correct 113 ms 5012 KB Output is correct
3 Correct 44 ms 4420 KB Output is correct
4 Correct 77 ms 4956 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 3924 KB Output is correct
2 Correct 111 ms 5316 KB Output is correct
3 Correct 165 ms 5624 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 4208 KB Output is correct