Submission #59157

#	Time	Username	Problem	Language	Result	Execution time	Memory
59157		Benq	Growing Trees (BOI11_grow)	C++14	100 / 100	289 ms	26232 KiB

grow

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int N,M;

template<class T, int SZ> struct LazySegTree {
    T mx[2*SZ], lazy[2*SZ]; // set SZ to a power of 2
    
    LazySegTree() {
        memset (mx,0,sizeof mx);
        memset (lazy,0,sizeof lazy);
    }
    
    void push(int ind, int L, int R) {
        mx[ind] += lazy[ind];
        if (L != R) lazy[2*ind] += lazy[ind], lazy[2*ind+1] += lazy[ind];
        lazy[ind] = 0;
    }
    
    void pull(int ind) {
        mx[ind] = max(mx[2*ind],mx[2*ind+1]);
    }
    
    void upd(int lo, int hi, int inc, int ind = 1, int L = 0, int R = -1) {
    	if (R == -1) R += N;

        push(ind,L,R);
        if (hi < L || R < lo) return;
        if (lo <= L && R <= hi) {
            lazy[ind] = inc;
            push(ind,L,R);
            return;
        }
        
        int M = (L+R)/2;
        upd(lo,hi,inc,2*ind,L,M); upd(lo,hi,inc,2*ind+1,M+1,R);
        pull(ind);
    }

    int getFst(int x, int ind = 1, int L = 0, int R = -1) {
    	if (R == -1) R += N;

    	push(ind,L,R);
    	if (L == R) {
    		if (mx[ind] >= x) return L;
    		return N;
    	}

    	int M = (L+R)/2;
    	push(2*ind,L,M);
    	if (mx[2*ind] >= x) return getFst(x,2*ind,L,M);
    	return getFst(x,2*ind+1,M+1,R);
    }

    int query(int x, int ind = 1, int L = 0, int R = -1) {
    	if (R == -1) R += N;

    	push(ind,L,R);
    	if (L == R) return mx[ind];
    	int M = (L+R)/2;
    	if (x <= M) return query(x,2*ind,L,M);
    	return query(x,2*ind+1,M+1,R);
    }
};

LazySegTree<int,1<<17> L;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    vi h(N);
    F0R(i,N) cin >> h[i];
    sort(all(h));
    F0R(i,N) L.upd(i,i,h[i]);

    F0R(i,M) {
        char t; cin >> t;
        if (t == 'F') {
            int c,h; cin >> c >> h;
            
            int x1 = L.getFst(h);
            if (x1 == N) continue;
            
            int x2 = min(x1+c-1,N-1);
            int val = L.query(x2);
            int a = L.getFst(val);
            int b = L.getFst(val+1)-1;
            
            L.upd(x1,a-1,1);
            L.upd(b-(x2-a),b,1);
        } else {
            int mn,mx; cin >> mn >> mx;
            cout << L.getFst(mx+1)-L.getFst(mn) << "\n";
        }
        // F0R(j,N) cout << L.query(j) << " ";
        // cout << "\n";
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

• 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