Submission #486586

#	Time	Username	Problem	Language	Result	Execution time	Memory
486586		Gurban	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	255 ms	105428 KiB

apple

#include "bits/stdc++.h"
using namespace std;
 
using ll = long long;

struct Node{
	int val,laz,l,r,lfc,rgc;
};

const int maxn=1e5+5;
int M,sz,C;
Node T[60*maxn];

void CL(int idx){
	sz++;
	T[sz].l = T[idx].l;
	T[sz].r = (T[idx].l + T[idx].r) / 2;
	
	T[idx].lfc = sz;
}
void CR(int idx){
	sz++;
	int md = (T[idx].l + T[idx].r) / 2;
	T[sz].l = md + 1;
	T[sz].r = T[idx].r;
	
	T[idx].rgc = sz;
}

void prop(int nd){
	if(T[nd].lfc == 0) CL(nd);
	if(T[nd].rgc == 0) CR(nd);
	
	if(T[nd].laz == 0) return;
	int lftC = T[nd].lfc;
	int rgtC = T[nd].rgc;
	T[lftC].val = T[lftC].r - T[lftC].l + 1;
	T[lftC].laz = 1;
	T[rgtC].val = T[rgtC].r - T[rgtC].l + 1;
	T[rgtC].laz = 1;
	T[nd].laz = 0;
}

void upd(int a,int b,int nd){
	if(T[nd].r < a or T[nd].l > b) return;
	if(T[nd].l >= a and T[nd].r <= b){
		T[nd].val = T[nd].r - T[nd].l + 1;
		T[nd].laz = 1;
		return;
	}
	prop(nd);
	upd(a,b,T[nd].lfc);
	upd(a,b,T[nd].rgc);
	T[nd].val = T[T[nd].lfc].val + T[T[nd].rgc].val;
}

int tap(int a,int b,int nd){
	if(T[nd].r < a or T[nd].l > b) return 0;
	if(T[nd].l >= a and T[nd].r <= b) return T[nd].val;
	prop(nd);
	return tap(a,b,T[nd].lfc) + tap(a,b,T[nd].rgc);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	sz = 1;
	T[1].l = 1;
	T[1].r = 1e9;
	
	cin >> M;
	while(M--){
		int tp,x,y; cin >> tp >> x >> y;
		if(tp == 1){
			int val = tap(x + C,y + C,1);
			cout<<val<<'\n';
			C = val;
		}
		else upd(x + C,y + C,1);
	}
}

• Subtask 1: 100 / 100