답안 #59157 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59157	2018-07-20T20:29:49 Z	Benq	Growing Trees (BOI11_grow)	C++14	100 / 100	289 ms	26232 KB

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.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	137 ms	2936 KB	Output is correct
2	Correct	200 ms	4588 KB	Output is correct
3	Correct	248 ms	6152 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	6152 KB	Output is correct
2	Correct	6 ms	6152 KB	Output is correct
3	Correct	7 ms	6152 KB	Output is correct
4	Correct	7 ms	6152 KB	Output is correct
5	Correct	58 ms	6200 KB	Output is correct
6	Correct	90 ms	6308 KB	Output is correct
7	Correct	11 ms	6308 KB	Output is correct
8	Correct	45 ms	6892 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	7064 KB	Output is correct
2	Correct	73 ms	8248 KB	Output is correct
3	Correct	7 ms	8248 KB	Output is correct
4	Correct	51 ms	8820 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	64 ms	8892 KB	Output is correct
2	Correct	80 ms	9852 KB	Output is correct
3	Correct	19 ms	9852 KB	Output is correct
4	Correct	89 ms	11204 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	121 ms	11204 KB	Output is correct
2	Correct	176 ms	12408 KB	Output is correct
3	Correct	26 ms	12444 KB	Output is correct
4	Correct	174 ms	13956 KB	Output is correct

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	165 ms	14044 KB	Output is correct
2	Correct	210 ms	15420 KB	Output is correct
3	Correct	285 ms	16968 KB	Output is correct
4	Correct	39 ms	16968 KB	Output is correct

Subtask #7
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	164 ms	17508 KB	Output is correct
2	Correct	171 ms	18568 KB	Output is correct
3	Correct	259 ms	19996 KB	Output is correct
4	Correct	32 ms	20292 KB	Output is correct

Subtask #8
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	263 ms	20624 KB	Output is correct
2	Correct	221 ms	20624 KB	Output is correct
3	Correct	92 ms	21120 KB	Output is correct
4	Correct	190 ms	22464 KB	Output is correct

Subtask #9
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	188 ms	22500 KB	Output is correct
2	Correct	233 ms	23940 KB	Output is correct
3	Correct	289 ms	25752 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	186 ms	26232 KB	Output is correct

답안 #59157

Compilation message