Submission #59156

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
59156	2018-07-20T20:18:58 Z	Benq	Growing Trees (BOI11_grow)	C++14	10 / 100	201 ms	17692 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);
            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;
            int len = x2-a+1;
            
            L.upd(x1,a-1,1);
            L.upd(b-len+1,b,1);
        } else {
            int mn,mx; cin >> mn >> mx;
            cout << L.getFst(mx+1)-L.getFst(mn) << "\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
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	181 ms	3968 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	3968 KB	Output is correct
2	Correct	7 ms	3968 KB	Output is correct
3	Correct	7 ms	3968 KB	Output is correct
4	Correct	6 ms	3980 KB	Output is correct
5	Correct	71 ms	5060 KB	Output is correct
6	Incorrect	79 ms	6164 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	77 ms	7240 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	78 ms	8036 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	144 ms	9200 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	179 ms	10396 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	162 ms	11260 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	201 ms	13068 KB	Output is correct
2	Incorrect	173 ms	14300 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	165 ms	15416 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	160 ms	17692 KB	Output is correct

Submission #59156

Compilation message