Submission #543288

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
543288	2022-03-30T03:48:39 Z	karthikhegde05	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	387 ms	188492 KB

apple

#include<bits/stdc++.h>
using namespace std;


#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>, 
    rb_tree_tag, tree_order_statistics_node_update>;

#define ook order_of_key
#define fbo find_by_order

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<long long> vll;
#define PI acos(-1.0)
#define EPS 1e-9
#define INF 1000000000
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define pb push_back
#define mkp make_pair
#define sqr(a) ((a) * (a))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define FOR(i, l, r) for(int i=int(l); i<=int(r); i++)
#define ROF(i, l, r) for(int i=int(r); i>=int(l); --i)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7;

void print_out(int x){
    cout<<"Case #"<<x<<": ";
}


struct Node{
	int sum, lazy, tl, tr, lc, rc;
	Node(): sum(0), lazy(0), lc(-1), rc(-1){}
};


const int MAXN = 123456;
Node segtree[64*MAXN];
int cnt = 2;

void push_lazy(int node){
	if(segtree[node].lazy){
		segtree[node].sum = (segtree[node].tr - segtree[node].tl +1)*segtree[node].lazy;
		int mid = (segtree[node].tl + segtree[node].tr)/2;

		if(segtree[node].lc==-1){
			segtree[node].lc = cnt++;
			segtree[segtree[node].lc].tl = segtree[node].tl;
			segtree[segtree[node].lc].tr = mid;
		}
		if(segtree[node].rc==-1){
			segtree[node].rc = cnt++;
			segtree[segtree[node].rc].tl = mid+1;
			segtree[segtree[node].rc].tr = segtree[node].tr;
		}

		segtree[segtree[node].lc].lazy = segtree[node].lazy;
		segtree[segtree[node].rc].lazy = segtree[node].lazy;
		segtree[node].lazy = 0;
	}
}


void update(int node, int inc, int l, int r){
	push_lazy(node);
	if(l==segtree[node].tl && segtree[node].tr==r){
		segtree[node].lazy = inc;
		push_lazy(node);
		return;
	}
	int mid = (segtree[node].tl + segtree[node].tr)/2;
	if(segtree[node].lc==-1){
		segtree[node].lc = cnt++;
		segtree[segtree[node].lc].tl = segtree[node].tl;
		segtree[segtree[node].lc].tr = mid;
	}
	if(segtree[node].rc==-1){
		segtree[node].rc = cnt++;
		segtree[segtree[node].rc].tl = mid+1;
		segtree[segtree[node].rc].tr = segtree[node].tr;
	}

	if(l>mid){
		update(segtree[node].rc, inc, l, r);
	}
	else if(r<=mid){
		update(segtree[node].lc, inc, l, r);
	}

	else{
		update(segtree[node].lc, inc, l, mid);
		update(segtree[node].rc, inc, mid+1, r);
	}

	push_lazy(segtree[node].lc);
	push_lazy(segtree[node].rc);

	segtree[node].sum = segtree[segtree[node].lc].sum + segtree[segtree[node].rc].sum;
}


int query(int node, int l, int r){
	push_lazy(node);
	if(l==segtree[node].tl && segtree[node].tr == r)
		return segtree[node].sum;
	
	int mid = (segtree[node].tl + segtree[node].tr)/2;
	if(segtree[node].lc==-1){
		segtree[node].lc = cnt++;
		segtree[segtree[node].lc].tl = segtree[node].tl;
		segtree[segtree[node].lc].tr = mid;
	}
	if(segtree[node].rc==-1){
		segtree[node].rc = cnt++;
		segtree[segtree[node].rc].tl = mid+1;
		segtree[segtree[node].rc].tr = segtree[node].tr;
	}

	if(l>mid){
		return query(segtree[node].rc, l, r);
	}
	if(r<=mid){
		return query(segtree[node].lc, l, r);
	}


	return query(segtree[node].lc, l, mid) + query(segtree[node].rc, mid+1, r);
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);


    int m;cin>>m;

	segtree[1].sum = 0;segtree[1].lazy = 0;
	segtree[1].tl = 1; segtree[1].tr = 1e9;

	int c = 0;
	FOR(i, 0, m-1){
		int d, x, y;cin>>d>>x>>y;
		if(d==1){
			c = query(1, x+c, y+c);
			cout<<c<<"\n";
		}
		else{
			update(1, 1, x+c, y+c);
		}
	}
    


    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	185804 KB	Output is correct
2	Correct	73 ms	185892 KB	Output is correct
3	Correct	73 ms	185756 KB	Output is correct
4	Correct	86 ms	185996 KB	Output is correct
5	Correct	91 ms	185932 KB	Output is correct
6	Correct	87 ms	186004 KB	Output is correct
7	Correct	89 ms	185932 KB	Output is correct
8	Correct	179 ms	186844 KB	Output is correct
9	Correct	317 ms	187984 KB	Output is correct
10	Correct	316 ms	188044 KB	Output is correct
11	Correct	313 ms	188064 KB	Output is correct
12	Correct	319 ms	187980 KB	Output is correct
13	Correct	282 ms	188348 KB	Output is correct
14	Correct	283 ms	188392 KB	Output is correct
15	Correct	378 ms	188448 KB	Output is correct
16	Correct	385 ms	188488 KB	Output is correct
17	Correct	291 ms	188436 KB	Output is correct
18	Correct	305 ms	188388 KB	Output is correct
19	Correct	387 ms	188408 KB	Output is correct
20	Correct	385 ms	188492 KB	Output is correct