oj.uz

답안 #484371

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
484371 2021-11-03T04:09:36 Z hoanghq2004 Growing Trees (BOI11_grow) C++17
0 / 100
 102 ms 6028 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);
}

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

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.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 6028 KB Output isn't correct