oj.uz

Submission #59157

# Submission time Handle Problem Language Result Execution time Memory
59157 2018-07-20T20:29:49 Z Benq Growing Trees (BOI11_grow) C++14
100 / 100
 289 ms 26232 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Correct 186 ms 26232 KB Output is correct