Submission #543290

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
543290	2022-03-30T04:01:26 Z	karthikhegde05	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	585 ms	262144 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;
	}

	
	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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	185808 KB	Output is correct
2	Correct	75 ms	185940 KB	Output is correct
3	Correct	73 ms	185728 KB	Output is correct
4	Correct	88 ms	185796 KB	Output is correct
5	Correct	99 ms	185856 KB	Output is correct
6	Correct	99 ms	185976 KB	Output is correct
7	Correct	88 ms	185836 KB	Output is correct
8	Correct	187 ms	185932 KB	Output is correct
9	Correct	324 ms	186160 KB	Output is correct
10	Correct	319 ms	186228 KB	Output is correct
11	Correct	317 ms	186180 KB	Output is correct
12	Correct	320 ms	186196 KB	Output is correct
13	Correct	300 ms	186300 KB	Output is correct
14	Correct	288 ms	186332 KB	Output is correct
15	Runtime error	585 ms	262144 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-