Submission #1307959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307959		ballbreaker	Growing Trees (BOI11_grow)	C++20	90 / 100	1095 ms	2344 KiB

grow

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
int a[100005];
int geti(int x) {
    return a[x];
}
void add(int l, int r) {
    for (int j = l; j <= r; j++) {
        a[j]++;
    }
}
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);
    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);
            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 l, r;
            cin >> l >> r;
            int ans = 0;
            for (int i = 1; i <= n; i++) {
                // cout << a[i] << ' ';
                if (l <= a[i] && a[i] <= r) {
                    ans++;
                }
            }
            // cout << endl;
            cout << ans << endl;

        }
    }
}

Compilation message (stderr)

grow.cpp:13:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   13 | 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: 0 / 10