Submission #842585

#	Time	Username	Problem	Language	Result	Execution time	Memory
842585		tuannm	Growing Trees (BOI11_grow)	C++17	100 / 100	116 ms	4024 KiB

grow

#include<bits/stdc++.h>
#define ii pair<int, int>
#define ll pair<long long, long long>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod[2] = {1000000007, 998244353};
const int N = 1e5 + 1;
const string NAME = "";
const int lim = 2147483647;
//const long long lim = 9223372036854775807;
const double pi = acos(-1);
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int n, m, a[N], tree[4 * N], bonus[4 * N];

void down(int s){
    int t = bonus[s];
    bonus[2 * s] += t;
    tree[2 * s] += t;
    bonus[2 * s + 1] += t;
    tree[2 * s + 1] += t;
    bonus[s] = 0;
}

void build(int s, int l, int r){
    if(l == r){
        tree[s] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * s, l, mid);
    build(2 * s + 1, mid + 1, r);
    tree[s] = max(tree[2 * s], tree[2 * s + 1]);
}

void update(int s, int l, int r, int u, int v, int val){
    if(v < l || u > r)
        return;
    if(u <= l && r <= v){
        tree[s] += val;
        bonus[s] += val;
        return;
    }
    int mid = (l + r) / 2;
    down(s);
    update(2 * s, l, mid, u, v, val);
    update(2 * s + 1, mid + 1, r, u, v, val);
    tree[s] = max(tree[2 * s], tree[2 * s + 1]);
}

int get_id(int s, int l, int r, int x){
    if(l == r){
        if(tree[s] >= x)
            return l;
        return n + 1;
    }
    int mid = (l + r) / 2;
    down(s);
    if(tree[2 * s] >= x)
        return get_id(2 * s, l, mid, x);
    return get_id(2 * s + 1, mid + 1, r, x);
}

int get(int s, int l, int r, int x){
    if(l == r)
        return tree[s];
    int mid = (l + r) / 2;
    down(s);
    if(x <= mid)
        return get(2 * s, l, mid, x);
    return get(2 * s + 1, mid + 1, r, x);
}

void inp(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
}

void solve(){
    sort(a + 1, a + n + 1);
    build(1, 1, n);
    while(m--){
        char c;
        int x, y;
        cin >> c >> x >> y;
        if(c == 'F'){
            int tmp1 = get_id(1, 1, n, y);
            if(tmp1 == n + 1)
                continue;
            int tmp2 = min(tmp1 + x - 1, n);
            int v = get(1, 1, n, tmp2);
            int p = get_id(1, 1, n, v);
            int q = get_id(1, 1, n, v + 1) - 1;
            update(1, 1, n, tmp1, p - 1, 1);
            update(1, 1, n, q - tmp2 + p, q, 1);
        }
        else{
            cout << get_id(1, 1, n, y + 1) - get_id(1, 1, n, x) << "\n";
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifdef TimeCalculation
        auto starttime = chrono::high_resolution_clock::now();
    #endif

    if(fopen((NAME + ".inp").c_str(), "r")){
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }

    inp();
    solve();

    #ifdef TimeCalculation
        auto endtime = chrono::high_resolution_clock::now();
        auto duration = chrono::duration_cast<chrono::milliseconds>(endtime - starttime).count();
        cout << "\n=====" << "\nTime elapsed: " << duration << " ms\n";
    #endif
}

/*
5 7
1 3 2 5 2
F 2 1
C 3 6
F 2 3
C 6 8
F 2 1
F 2 2
C 3 5
*/

Compilation message (stderr)

grow.cpp: In function 'int main()':
grow.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         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