Submission #543292

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
543292	2022-03-30T04:11:20 Z	karthikhegde05	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	386 ms	186540 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].tl!=segtree[node].tr){

			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(r<segtree[node].tl || segtree[node].tr<l)return;
	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, r);
		update(segtree[node].rc, inc, l, 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(r<segtree[node].tl || segtree[node].tr<l)return 0;
	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, r) + query(segtree[node].rc, l, 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	80 ms	185804 KB	Output is correct
2	Correct	74 ms	185776 KB	Output is correct
3	Correct	77 ms	185772 KB	Output is correct
4	Correct	91 ms	185804 KB	Output is correct
5	Correct	98 ms	185864 KB	Output is correct
6	Correct	95 ms	185792 KB	Output is correct
7	Correct	92 ms	185780 KB	Output is correct
8	Correct	189 ms	186000 KB	Output is correct
9	Correct	297 ms	186172 KB	Output is correct
10	Correct	304 ms	186144 KB	Output is correct
11	Correct	312 ms	186196 KB	Output is correct
12	Correct	309 ms	186212 KB	Output is correct
13	Correct	281 ms	186356 KB	Output is correct
14	Correct	285 ms	186328 KB	Output is correct
15	Correct	374 ms	186436 KB	Output is correct
16	Correct	386 ms	186256 KB	Output is correct
17	Correct	286 ms	186316 KB	Output is correct
18	Correct	284 ms	186260 KB	Output is correct
19	Correct	381 ms	186540 KB	Output is correct
20	Correct	372 ms	186256 KB	Output is correct