Submission #339080

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
339080	2020-12-24T14:39:40 Z	amunduzbaev	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	531 ms	138988 KB

apple

/** made by amunduzbaev **/
#include <bits/stdc++.h>

using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}

const int N = 1e9+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
int s, n, m, k, ans, cur;

struct node{
	int sum, lz;
	node *lx, *rx;
	
	node(){
		sum = 0, lz = 0;
		lx = NULL;
		rx = NULL;
	}
	
};

void prop(node *x, int len){
	if(x->lz){
		if(x->lx != NULL) x->lx->lz = 1;
		if(x->rx != NULL) x->rx->lz = 1;
		x->sum = len;
	}
}

void update(node *x, int l, int r, int lx, int rx){
	int m = (lx + rx)/2;
	prop(x, rx - lx +1);
	
	if(lx > r || rx < l) return;
	if(lx >= l && rx <= r){
		x->lz = 1;
		prop(x, rx-lx+1);
		return;
	}
	if(x->lx == NULL) x->lx = new node();
	if(x->rx == NULL) x->rx = new node();
	
	prop(x, rx - lx +1);
	update(x->lx, l, r, lx, m);
	update(x->rx, l, r, m+1, rx);
	x->sum = x->lx->sum + x->rx->sum;
}

int qq(node *x, int l, int r, int lx, int rx){
	int m = (lx + rx)/2;
	prop(x, rx - lx+1);
	
	if(lx > r || rx < l) return 0;
	if(lx >= l && rx <= r) return x->sum;
	
	if(x->lx == NULL) x->lx = new node();
	if(x->rx == NULL) x->rx = new node();
	prop(x, rx - lx +1);
	
	int res = qq(x->lx, l, r, lx, m);
	res += qq(x->rx, l, r, m+1, rx);
	x->sum = x->lx->sum + x->rx->sum;
	return res;
}

void solve(){
	fastios
	cin>>m;
	int c = 0;
	node *root = new node();
	for(int i=0;i<m;i++){
		int t;
		cin>>t;
		if(t == 1){
			int l, r;
			cin>>l>>r;
			c = qq(root, l+c, r+c, 1, N);
			cout<< c <<"\n";
		}else{
			int l, r;
			cin>>l>>r;
			update(root, l+c, r+c, 1, N);
		}
	}
	return;
}

int main(){
	fastios
	int t = 1;
	if(t) solve();
	else {
		cin>>t;
		while (t--) solve();
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	17 ms	3564 KB	Output is correct
5	Correct	22 ms	4204 KB	Output is correct
6	Correct	24 ms	4076 KB	Output is correct
7	Correct	21 ms	4204 KB	Output is correct
8	Correct	167 ms	30188 KB	Output is correct
9	Correct	349 ms	52076 KB	Output is correct
10	Correct	361 ms	57568 KB	Output is correct
11	Correct	367 ms	61676 KB	Output is correct
12	Correct	370 ms	63724 KB	Output is correct
13	Correct	338 ms	73964 KB	Output is correct
14	Correct	339 ms	74604 KB	Output is correct
15	Correct	521 ms	135020 KB	Output is correct
16	Correct	517 ms	135788 KB	Output is correct
17	Correct	341 ms	76396 KB	Output is correct
18	Correct	344 ms	76652 KB	Output is correct
19	Correct	531 ms	138988 KB	Output is correct
20	Correct	520 ms	138860 KB	Output is correct