Submission #1307962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307962		ballbreaker	Growing Trees (BOI11_grow)	C++20	100 / 100	135 ms	2356 KiB

grow

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
int a[100005];
int f[100005];
void upd(int v, int val) {
    for (; v <= 100001; v = (v | (v + 1))) {
        f[v] += val;
    }
}
int get(int v) {
    int sum = 0;
    for (; v >= 0; v = (v & (v + 1)) - 1) {
        sum += f[v];
    }
    return sum;
}
int geti(int x) {
    return get(x);;
}
void add(int l, int r) {
    upd(l, 1);
    upd(r + 1, -1);
}
main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int m;
    cin >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        upd(i, a[i] - a[i - 1]);
        // cout << get(i) << ' ';
    }
    // cout << endl;
    while (m--) {
        char t;
        cin >> t;
        if (t == 'F') {
            int c, h;
            cin >> c >> h;
            int l = 1, r = n + 1;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (geti(mid) >= h) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            if (l == n + 1) {
                continue;
            }
            int st = l;
            c = min(c, n - st + 1);
            int val = geti(st + c - 1);
            int pos;
            {
                int l = st - 1, r = n;
                while (l < r) {
                    int mid = (l + r + 1) >> 1;
                    if (geti(mid) < val) {
                        l = mid;
                    } else {
                        r = mid - 1;
                    }
                }
                pos = l;
            }
            add(st, pos);
            // cout << st << ' ' << pos << endl;
            int rem = c - (pos - st + 1);
            l = pos + 1, r = n;
            while (l < r) {
                int mid = (l + r + 1) >> 1;
                if (geti(mid) == val) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            int poss = l;
            add(poss - rem + 1, poss);
            // cout << st << ' ' << pos << endl;
        } else {
            int a, b;
            cin >> a >> b;
            int ans = 0;
            {
                int l = 0, r = n;
                while (l < r) {
                    int mid = (l + r + 1) >> 1;
                    if (geti(mid) < a) {
                        l = mid;
                    } else {
                        r = mid - 1;
                    }
                }
                ans -= l;
            }
            {
                int l = 0, r = n;
                while (l < r) {
                    int mid = (l + r + 1) >> 1;
                    if (geti(mid) <= b) {
                        l = mid;
                    } else {
                        r = mid - 1;
                    }
                }
                ans += l;
            }
            // cout << endl;
            cout << ans << endl;

        }
    }
}

Compilation message (stderr)

grow.cpp:25:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | main() {
      | ^~~~

• 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