Submission #842714

#	Time	Username	Problem	Language	Result	Execution time	Memory
842714		tuannm	Growing Trees (BOI11_grow)	C++17	0 / 100	521 ms	3916 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 = "g";
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];

#ifdef i128
ostream & operator << (ostream &out, const __int128 &x){
    __int128 i = x;
    vector<int> digits;
    while(i > 0){
        digits.pb(i % 10);
        i /= 10;
    }
    reverse(digits.begin(), digits.end());
    for(auto x : digits)
        out << x;
    return out;
}
#endif

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(int s, int l, int r, int u, int v){
    if(v < l || u > r)
        return 0;
    if(u <= l && r <= v)
        return tree[s];
    int mid = (l + r) / 2;
    down(s);
    return max(get(2 * s, l, mid, u, v), get(2 * s + 1, mid + 1, r, u, v));
}

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 l = 1, r = n;
            if(get(1, 1, n, n, n) < y)
                continue;
            int idx = 1;
            while(l <= r){
                int mid = (l + r) / 2;
                if(get(1, 1, n, mid, mid) >= y){
                    idx = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
//            cout << idx << "\n";
            if(idx + x - 1 > n){
                update(1, 1, n, idx, n, 1);
            }
            else{
                int tmp = get(1, 1, n, idx + x - 1, idx + x - 1) + 1;
                if(tmp <= get(1, 1, n, idx + x, idx + x)){
                    update(1, 1, n, idx, idx + x - 1, 1);
                }
                else{
                    int tmp2 = tmp - 1;
                    int L = idx, R = n;
                    l = 1, r = n;
                    while(l <= r){
                        int mid = (l + r) / 2;
                        if(get(1, 1, n, mid, mid) >= tmp2){
                            L = mid;
                            r = mid - 1;
                        }
                        else l = mid + 1;
                    }
                    l = 1, r = n;
                    while(l <= r){
                        int mid = (l + r) / 2;
                        if(get(1, 1, n, mid, mid) <= tmp2){
                            R = mid;
                            l = mid + 1;
                        }
                        else r = mid - 1;
                    }
                    update(1, 1, n, idx, idx + x - 1, 1);
                    update(1, 1, n, L, idx + x - 1, -tmp);
                    update(1, 1, n, L, idx + x - 1, tmp2);
                    update(1, 1, n, idx + x, R, -tmp2);
                    update(1, 1, n, idx + x, R, tmp);
                }
            }
        }
        else{
            int l = 1, r = n;
            int L = 1, R = n;
            while(l <= r){
                int mid = (l + r) / 2;
                if(get(1, 1, n, mid, mid) >= x){
                    L = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            l = 1, r = n;
            while(l <= r){
                int mid = (l + r) / 2;
                if(get(1, 1, n, mid, mid) <= y){
                    R = mid;
                    l = mid + 1;
                }
                else r = mid - 1;
            }
            if(get(1, 1, n, L, L) > y || get(1, 1, n, R, R) < x){
                cout << "0\n";
            }
            else{
//                cout << L << " " << R << "\n";
                cout << R - L + 1 << "\n";
            }
        }
//        for(int i = 1; i <= n; ++i){
//            cout << get(1, 1, n, i, i) << " ";
//        }
//        cout << "\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:186:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp:187:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |         freopen((NAME + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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