Submission #971134

#	Time	Username	Problem	Language	Result	Execution time	Memory
971134		NoLove	Growing Trees (BOI11_grow)	C++14	0 / 100	81 ms	9664 KiB

grow

/**
 *    author : Lăng Trọng Đạt
 *    created: 28-04-2024 
**/
#include <bits/stdc++.h>
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
#define int long long
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define all(v) (v).begin(), (v).end()
using pii = pair<int, int>;
using vi = vector<int>;
#define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
void mx(int& a, int b) { if (b > a) a = b; }
void mi(int& a, int b) { if (b < a) a = b; }
#define si(x) (int)(x.size())
const int INF = 1e18;
const int MOD = 1e9 + 7;

const int MAXN = 1e5 + 5;
int g[MAXN];
int n;

struct Node {
    int add = 0, mx = 0;
} st[4*MAXN];

void build(int v = 1, int l = 1, int r = n) {
    if (l == r) st[v].mx = g[l];
    else {
        int mid = (l + r) / 2;
        build(2*v, l, mid);
        build(2*v + 1, mid + 1, r);
        st[v].mx = max(st[2*v].mx, st[2*v + 1].mx);
    }
}

void push(int v, int l, int r) {
    st[v].mx += st[v].add;
    if (l < r) {
        st[2*v].add += st[v].add;
        st[2*v + 1].add += st[v].add;
    }
    st[v].add = 0;
}
void upd(int p, int q, int v = 1, int l = 1, int r = n) {
    if (l > q or p > r) return;
    if (p <= l && r <= q) {
        st[v].add++;
    }
    else {
        int mid = (l + r) / 2;
        upd(p, q, 2*v, l, mid);
        upd(p, q, 2*v + 1, mid + 1, r);
        push(2*v, l, mid);
        push(2*v + 1, mid + 1, r);
        st[v].mx = max(st[2*v].mx, st[2*v + 1].mx);
    }
}

int get_index(int x, int v = 1, int l = 1, int r = n) {
    push(v, l, r);
    x -= st[v].add;
    if (l == r) return (x > st[v].mx ? n + 1 : l);
    int mid = (l + r) / 2;
    if (x <= st[2*v].mx) {
        return get_index(x, 2*v, l, mid);
    } else {
        return get_index(x, 2*v + 1, mid + 1, r);
    }
}
int get_val(int p, int v = 1, int l = 1, int r = n) {
    push(v, l, r);
    if (l > p or p > r) return 0;
    if (l == r) return st[v].mx;
    else {
        int mid = (l + r) / 2;
        return get_val(p, 2*v, l, mid) + get_val(p, 2*v + 1, mid + 1, r);
    }
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    if (fopen("hi.inp", "r")) {
        freopen("hi.inp", "r", stdin);
//        freopen("hi.out", "w", stdout);
    } 

    int m, c, h;
    char type;
    cin >> n >> m;
    FOR(i, 1, n) {
        cin >> g[i];
    }   
    sort(g, g + n + 1);
    build();
    FOR(i, 1, m) {
        cin >> type >> c >> h;
        if (type == 'F') {
            int l_id = get_index(h);
            db(l_id)
            if (l_id + c - 1 >= n) {
                upd(l_id, n);                
            } else {
                int r_val = get_val(l_id + c);
                int vach = get_index(r_val) - 1;
                if (l_id <= vach)
                    upd(l_id, vach);
                int cuoi = get_index(r_val + 1) - 1;
                upd(cuoi - (c - (vach - l_id + 1)) + 1, cuoi);
                db(c, h, l_id, r_val, cuoi, vach)
                db(cuoi - (c - (vach - l_id + 1)) + 1)
            }
        } else {
            db(c, h, get_index(c), get_index(h))
            cout << get_index(h + 1) - get_index(c) << "\n"; 
        }
    }
}

Compilation message (stderr)

grow.cpp: In function 'int32_t main()':
grow.cpp:18:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
grow.cpp:97:5: note: in expansion of macro 'FOR'
   97 |     FOR(i, 1, n) {
      |     ^~~
grow.cpp:18:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
grow.cpp:102:5: note: in expansion of macro 'FOR'
  102 |     FOR(i, 1, m) {
      |     ^~~
grow.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen("hi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 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