Submission #1159027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159027		ByeWorld	Growing Trees (BOI11_grow)	C++20	100 / 100	105 ms	4420 KiB

grow

#include <bits/stdc++.h>
// #define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<pii,int> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 2e5+10;
const int SQRT = 300;
const int MAXA = 50;
const int LOG = 20;
const int INF = 1e12+10;
const ld EPS = 1e-6;
const int MOD = 998244353;
int sum(int a, int b){ return (a+b)%MOD; }
void chsum(int &a, int b){ a = (a+b)%MOD; }
void chsub(int &a, int b){ a = (a+MOD-b)%MOD; }
int mul(int a, int b){ return (a*b)%MOD; }
void chmul(int &a, int b){ a = (a*b)%MOD; }
void chmn(int &a, int b){ a = min(a, b); }
void chmx(int &a, int b){ a = max(a, b); }

int n, q, a[MAXN];

struct seg {
    int st[4*MAXN], mx[4*MAXN], laz[4*MAXN];
    void bd(int id, int l, int r){
        if(l==r){ st[id] = mx[id] = a[l]; return; }
        bd(lf,l,md); bd(rg,md+1,r);
        st[id] = min(st[lf], st[rg]);
        mx[id] = max(mx[lf], mx[rg]);
    }
    void bnc(int id, int l, int r){
        if(laz[id]==0) return;
        st[lf] += laz[id]; mx[lf] += laz[id]; laz[lf] += laz[id]; 
        st[rg] += laz[id]; mx[rg] += laz[id]; laz[rg] += laz[id];
        laz[id] = 0;
    }
    void upd(int id,int l,int r,int x,int y,int p){
        if(x<=l && r<=y){
            laz[id] += p; mx[id] += p; st[id] += p;
            return;
        }
        if(r<x || y<l) return;
        bnc(id,l,r);
        upd(lf,l,md,x,y,p); upd(rg,md+1,r,x,y,p);
        st[id] = min(st[lf], st[rg]); mx[id] = max(mx[lf], mx[rg]);
    }
    int que(int id, int l, int r, int x, int y){
        if(l==r && l==x) return st[id];
        if(r<x || y<l) return INF;
        bnc(id,l,r);
        return min(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
    }
    void out(int id, int l, int r){
        if(l==r){ cout << st[id] << ' '; return; }
        bnc(id,l,r);
        out(lf,l,md); out(rg,md+1,r);
    }
    int cari(int id,int l,int r,int val){
        if(l==r){
            if(st[id] >= val) return l;
            return INF; // gk memenuhi
        }
        if(mx[id] < val) return INF; // out 
        if(st[id] >= val) return l; // udh bisa
        bnc(id,l,r);
        // cek kanan cukup
        return min(cari(lf,l,md,val), cari(rg,md+1,r,val));
    }
    int bin(int val){
        return min(n+1, cari(1,1,n,val));
    }
} A;

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1; i<=n; i++) cin >> a[i];
    sort(a+1,a+n+1);
    A.bd(1,1,n);
    while(q--){
        char x; int l,r;cin>>x>>l>>r;
        if(x=='C'){
            cout << A.bin(r+1)-A.bin(l) << '\n';
        } else {
            int num = l, hei = r;
            int id = A.bin(hei);
            if(id+num-1 >= n){
                A.upd(1,1,n,id,n,1);
            } else {
                int val = A.que(1,1,n,id+num-1,id+num-1);
                int en = A.bin(val), atas = A.bin(val+1);
                A.upd(1,1,n,id,en-1,1);

                int sis = num - (en-id);
                A.upd(1,1,n,atas-sis,atas-1,1);
            }
        }
        // A.out(1,1,n); cout << " pp\n";
    }
}

Compilation message (stderr)

grow.cpp:20:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.00000000001e+12' to '2147483647' [-Woverflow]
   20 | const int INF = 1e12+10;
      |                 ~~~~^~~

• 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