Submission #543291

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
543291	2022-03-30T04:08:21 Z	karthikhegde05	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	555 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	78 ms	185932 KB	Output is correct
2	Correct	80 ms	185840 KB	Output is correct
3	Correct	75 ms	185840 KB	Output is correct
4	Correct	85 ms	185768 KB	Output is correct
5	Correct	89 ms	185804 KB	Output is correct
6	Correct	95 ms	185776 KB	Output is correct
7	Correct	91 ms	185876 KB	Output is correct
8	Correct	200 ms	185984 KB	Output is correct
9	Correct	318 ms	186164 KB	Output is correct
10	Correct	323 ms	186268 KB	Output is correct
11	Correct	322 ms	186236 KB	Output is correct
12	Correct	332 ms	186372 KB	Output is correct
13	Correct	298 ms	186448 KB	Output is correct
14	Correct	295 ms	186324 KB	Output is correct
15	Runtime error	555 ms	262144 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-