Submission #1165452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165452		dzhoz0	Growing Trees (BOI11_grow)	C++20	100 / 100	64 ms	1604 KiB

grow

/*
    ghmt the cutie :3
          UwU
*/

#include <bits/stdc++.h>
using namespace std;

#define INF 1e18
#define f first
#define s second
#define pii pair<int, int>
#define vi vector<int>

const int MOD = 1'000'000'000 + 7;

void setIO(string name = "")
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
#ifdef LOCAL
    freopen("inp.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    if (!name.empty())
    {
        freopen((name + ".INP").c_str(), "r", stdin);
        freopen((name + ".OUT").c_str(), "w", stdout);
    }
#endif
}

const int MAXN = 1e5;

int n;
int bit[MAXN + 5];

void upd(int pos, int val) {
    while(pos <= n) {
        bit[pos] += val;
        pos += pos & (-pos);
    }
}

void upd_range(int l, int r) {
    upd(l, 1);
    upd(r + 1, -1);
}

int query(int pos) {
    int res = 0;
    while(pos > 0) {
        res += bit[pos];
        pos -= pos & (-pos);
    }
    return res;
}

int upper_bound(int l, int r, int val) {
    int res = r + 1;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(query(mid) > val) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    return res;
}

int lower_bound(int l, int r, int val) {
    int res = r + 1;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(query(mid) >= val) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    return res;
}


void solve()
{
    cin >> n;
    int q; cin >> q;
    vi a(n); for(int &i : a) cin >> i;
    sort(a.begin(), a.end());
    for(int i = 1; i <= n; i++) {
        upd(i, a[i - 1]);
        upd(i + 1, -a[i - 1]);
    }

    while(q--) {
        char op; cin >> op;
        // cout << "a[]: "; for(int i = 1; i <= n; i++) cout << query(i) << ' '; cout << '\n';
        if(op == 'F') {
            int c, h; cin >> c >> h;

            int l = lower_bound(1, n, h);
            int r = l + c - 1;

            // cout << l << ' ' << r << '\n';

            if(r >= n) {
                upd_range(l, r);
                continue;
            }

            int pivot = query(r + 1);
            int lopi = lower_bound(l, r, pivot);

            // cout << db(pivot) << '\n';

            if(lopi == r + 1) {
                upd_range(l, r);
                continue;
            }
            
            if(lopi > l) upd_range(l, lopi - 1);
            int rem = c - (lopi - l);
            int lst = upper_bound(l, n, pivot) - 1;
            int rr = lst;
            int ll = lst - rem + 1;
            upd_range(ll, rr);
            
        }
        else {
            int l, r; cin >> l >> r;
            cout << upper_bound(1, n, r) - lower_bound(1, n, l) << '\n';
        }
    }
}
signed main()
{
    setIO();
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

Compilation message (stderr)

grow.cpp: In function 'void setIO(std::string)':
grow.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen((name + ".INP").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name + ".OUT").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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