Submission #846580

#	Time	Username	Problem	Language	Result	Execution time	Memory
846580		LTTrungCHL	Growing Trees (BOI11_grow)	C++17	10 / 100	93 ms	5972 KiB

grow

///***LTT***///
/// ->TUYEN QUOC GIA<- ///
#include<bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
//#define int long long
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define CHECKBIT(mask,i) ((mask>>(i) )&1) // == 1 la bat, == 0 la tat
#define OFFBIT(mask,i) ((1<<(i))^mask) // tat bit thu i
#define ONBIT(mask,i) ((1<<(i))mask) // bat bit thu i
using namespace std;
const long long oo = 1e9+7;
const int N = 1e5 + 10;
pair <int, int> tree[N * 4];
int lazy[N * 4];
int a[N], n, q;
char type;
void build(int id,int l,int r){
    if (l == r){
        tree[id].F = a[l];
        tree[id].S = a[l];
        return;
    }
    int mid = (l + r)/2;
    build(id*2,l,mid);
    build(id*2 + 1,mid + 1,r);
    tree[id].F = max(tree[id * 2].F, tree[id * 2 + 1].F);
    tree[id].S = min(tree[id * 2].S, tree[id * 2 + 1].S);
    return;
}
void down(int id,int l,int r){
    if (l != r){
        tree[id*2].F += lazy[id];
        tree[id*2 + 1].F += lazy[id];
        tree[id*2 + 1].S += lazy[id];
        tree[id*2 ].S += lazy[id];
        lazy[id*2] += lazy[id];
        lazy[id*2 + 1] += lazy[id];
    }
    lazy[id] = 0;
}
int cnpl(int id,int l,int r,int k){
    if (lazy[id]){
        down(id,l,r);
    }
    if (l == r){
        if (tree[id].F < k) return n + 1;
        return r;
    }
    int mid = (l + r)/2;
    if (tree[id * 2].F >= k) return cnpl(id * 2,l,mid,k);
    return cnpl(id * 2 + 1,mid + 1,r,k);
}
int cnpr(int id,int l,int r,int k){
    if (lazy[id]){
        down(id,l,r);
    }
    if (l == r){
        return r;
    }
    int mid = (l + r)/2;
    if (tree[id * 2 + 1].S <= k) return cnpr(id * 2 + 1,mid + 1,r,k);
    return cnpr(id * 2 ,l,mid ,k);
}
void update(int id,int l,int r,int u,int v){
    if (lazy[id]){
        down(id,l,r);
    }
    if (l > v or r < u) return;
    if (l >= u and r <= v){
        tree[id].F++;
        tree[id].S++;
        lazy[id]++;
        return;
    }
    int mid = (l + r)/2;
    update(id * 2,l,mid,u,v);
    update(id * 2 + 1,mid + 1,r,u,v);
    tree[id].F = max(tree[id * 2].F, tree[id * 2 + 1].F);
    tree[id].S = min(tree[id * 2].S, tree[id * 2 + 1].S);
    return;
}
int get(int id,int l,int r,int u){
    if (lazy[id]){
        down(id,l,r);
    }
    if (l > u or r < u) return 0;
    if (l == u and r == u){
        return tree[id].F;
    }
    int mid = (l + r)/2;
    return max(get(id*2,l,mid,u), get(id*2+1,mid+1,r,u));

}
void inp(){
    cin >> n >> q;
    for (int i = 1;i <= n;i++){
        cin >> a[i];
    }
    return;
}
void solve(){
    sort(a + 1, a + n + 1);
    build(1,1,n);
    for (int i = 1;i <= q;i++){
        cin >> type;
        if (type == 'F'){
                int h, c;
            cin >> c >> h;
            int l = cnpl(1,1,n,h);
            int nxt = 0;
            if (l + c - 1< n){
                int val = get(1,1,n,l + c - 1);
                nxt = cnpl(1,1,n,val);
                if (nxt - 1 >= l)
                update(1,1,n,l, nxt - 1);
                int sl = (l + c - 1) - nxt + 1;
                if (get(1,1,n,l + c) == val){
                    int r = cnpr(1,1,n,val);
                    update(1,1,n,r - sl + 1, r);
                } else update(1,1,n,nxt,nxt + ((l + c - 1) - nxt));
            } else update(1,1,n,l, min(n, l + c - 1));
        } else {
            int l, r;
            cin >> l >> r;
            r = cnpr(1,1,n,r);
            l = cnpl(1,1,n,l);
            cout << r - l + 1 <<"\n";
        }
    }
    return;
}
int main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    if (fopen("file.inp", "r")){
        freopen("file.inp", "r", stdin);
        freopen("file.out", "w", stdout);
    }
    //int t;
    //cin >> t;
    //while(t--){
    inp();
    solve();
    //}
}

Compilation message (stderr)

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