oj.uz

Submission #625360

# Submission time Handle Problem Language Result Execution time Memory
625360 2022-08-10T09:12:18 Z Duy_e Growing Trees (BOI11_grow) C++14
100 / 100
 143 ms 4536 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "test"
using namespace std;
const long long INF = 1e18;
const long long N = 2e5 + 5;

int n, m, h[N], ma[4 * N], mi[4 * N], lazy[4 * N];

void build(int id, int l, int r) {
    if (l == r) {
        ma[id] = mi[id] = h[l];
        return;
    }

    int mid = l + r >> 1;
    build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r);

    ma[id] = max(ma[id << 1], ma[id << 1 | 1]);
    mi[id] = min(mi[id << 1], mi[id << 1 | 1]);
}

void down(int id) {
    int &t = lazy[id], u = id << 1, v = id << 1 | 1;
    ma[u] += t; ma[v] += t;
    mi[u] += t; mi[v] += t;
    lazy[u] += t; lazy[v] += t;
    t = 0;
}

void upd(int id, int l, int r, int lef, int rig) {
    if (l > rig || r < lef) return;
    if (lef <= l && r <= rig) {
        ma[id] ++;
        mi[id] ++;
        lazy[id] ++;
        return;
    }

    down(id);
    int mid = l + r >> 1;
    upd(id << 1, l, mid, lef, rig);
    upd(id << 1 | 1, mid + 1, r, lef, rig);

    ma[id] = max(ma[id << 1], ma[id << 1 | 1]);
    mi[id] = min(mi[id << 1], mi[id << 1 | 1]);
}

ll getFirst(int id, int l, int r, int x) {
    if (l == r) return ma[id] >= x ? l : l + 1;
    int u = id << 1, v = id << 1 | 1, mid = l + r >> 1;

    down(id);

    if (ma[u] >= x) return getFirst(u, l, mid, x);
    return getFirst(v, mid + 1, r, x);
}

ll getLast(int id, int l, int r, int x)  {
    if (l == r) return mi[id] <= x ? l : l - 1;
    int u = id << 1, v = id << 1 | 1, mid = l + r >> 1;

    down(id);

    if (mi[v] <= x) return getLast(v, mid + 1, r, x);
    return getLast(u, l, mid, x);
}

ll getPos(int id, int l, int r, int i) {
    if (l == r) return ma[id];
    down(id);
    int mid = l + r >> 1;
    if (mid >= i) return getPos(id << 1, l, mid, i);
    return getPos(id << 1 | 1, mid + 1, r, i);
}

void queries(int C = 0, int H = 0) {

    if (getPos(1, 1, n, n) < H) return;

    int L = getFirst(1, 1, n, H);

    if (L + C - 1 > n) {
        upd(1, 1, n, L, n);
        return;
    }

    int val = getPos(1, 1, n, L + C - 1);
    int R = getLast(1, 1, n, val);


    int r = L - 1;
    if (getPos(1, 1, n, L) < val) r = getLast(1, 1, n, val - 1);

    if (r >= L) upd(1, 1, n, L, r);
    int len = r - L + 1;
    upd(1, 1, n, R - (C - len) + 1, R);

}

void answer(int L, int R) {
    cout << getLast(1, 1, n, R) - getFirst(1, 1, n, L) + 1 << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    // #endif

    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        cin >> h[i];
    sort(h + 1, h + 1 + n);

    build(1, 1, n);

    char t; int l, r;
    for (int i = 1; i <= m; i ++) {
        cin >> t >> l >> r;
        if (t == 'F') queries(l, r);
        if (t == 'C') answer(l, r);
    }

    return 0;
}    
/**  /\_/\
*   (= ._.)
*   / >🍵 \>🍮
**/

Compilation message

grow.cpp:131:9: warning: "/*" within comment [-Wcomment]
  131 | /**  /\_/\
      |          
grow.cpp: In function 'void build(int, int, int)':
grow.cpp:19:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |     int mid = l + r >> 1;
      |               ~~^~~
grow.cpp: In function 'void upd(int, int, int, int, int)':
grow.cpp:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     int mid = l + r >> 1;
      |               ~~^~~
grow.cpp: In function 'long long int getFirst(int, int, int, int)':
grow.cpp:54:47: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     int u = id << 1, v = id << 1 | 1, mid = l + r >> 1;
      |                                             ~~^~~
grow.cpp: In function 'long long int getLast(int, int, int, int)':
grow.cpp:64:47: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     int u = id << 1, v = id << 1 | 1, mid = l + r >> 1;
      |                                             ~~^~~
grow.cpp: In function 'long long int getPos(int, int, int, int)':
grow.cpp:75:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 4240 KB Output is correct
2 Correct 100 ms 4136 KB Output is correct
3 Correct 102 ms 4044 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 37 ms 904 KB Output is correct
6 Correct 47 ms 1040 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 27 ms 984 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1132 KB Output is correct
2 Correct 44 ms 1092 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 29 ms 960 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1188 KB Output is correct
2 Correct 50 ms 1148 KB Output is correct
3 Correct 9 ms 672 KB Output is correct
4 Correct 47 ms 1160 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 2552 KB Output is correct
2 Correct 85 ms 4048 KB Output is correct
3 Correct 13 ms 1624 KB Output is correct
4 Correct 78 ms 3928 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 4096 KB Output is correct
2 Correct 109 ms 4164 KB Output is correct
3 Correct 94 ms 3916 KB Output is correct
4 Correct 12 ms 1492 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 4160 KB Output is correct
2 Correct 66 ms 4192 KB Output is correct
3 Correct 96 ms 3964 KB Output is correct
4 Correct 12 ms 1492 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 4156 KB Output is correct
2 Correct 94 ms 4016 KB Output is correct
3 Correct 26 ms 4028 KB Output is correct
4 Correct 65 ms 4056 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 4256 KB Output is correct
2 Correct 93 ms 4048 KB Output is correct
3 Correct 143 ms 4012 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 4536 KB Output is correct