Submission #543289

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
543289	2022-03-30T03:55:18 Z	karthikhegde05	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	547 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].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	71 ms	185720 KB	Output is correct
2	Correct	76 ms	185852 KB	Output is correct
3	Correct	75 ms	185840 KB	Output is correct
4	Correct	90 ms	185824 KB	Output is correct
5	Correct	89 ms	185864 KB	Output is correct
6	Correct	89 ms	185864 KB	Output is correct
7	Correct	89 ms	185824 KB	Output is correct
8	Correct	187 ms	185984 KB	Output is correct
9	Correct	342 ms	186216 KB	Output is correct
10	Correct	322 ms	186288 KB	Output is correct
11	Correct	326 ms	186176 KB	Output is correct
12	Correct	321 ms	186208 KB	Output is correct
13	Correct	294 ms	186296 KB	Output is correct
14	Correct	293 ms	186308 KB	Output is correct
15	Runtime error	547 ms	262144 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-