Submission #625358

#	Time	Username	Problem	Language	Result	Execution time	Memory
625358		Duy_e	Growing Trees (BOI11_grow)	C++14	100 / 100	139 ms	6004 KiB

grow

#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);

    // cout << "L: " << L << ", R: " << R << ", r: " << r << '\n';
}

void answer(int L, int R) {
    // for (int i = 1; i <= n; i ++) cout << getPos(1, 1, n, i) << ' ';
    // cout << '\n';
    // cout << "L, R: " << L << ' ' << R << '\n';
    // cout << getLast(1, 1, n, R) << ' ' << getFirst(1, 1, n, L) << '\n';
    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 j = 1; j <= n; j ++)
    //     cout << getPos(1, 1, n, j) << ' ';
    // cout << '\n';

    for (int i = 1; i <= m; i ++) {
        cin >> t >> l >> r;
        if (t == 'F') queries(l, r);
        if (t == 'C') answer(l, r);
    
        // for (int j = 1; j <= n; j ++)
        //     cout << getPos(1, 1, n, j) << ' ';
        // cout << '\n';

    }

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

Compilation message (stderr)

grow.cpp:146:9: warning: "/*" within comment [-Wcomment]
  146 | /**  /\_/\
      |          
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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10