Submission #963732

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
963732	2024-04-15T14:43:31 Z	ByeWorld	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	535 ms	207808 KB

apple

#include <bits/stdc++.h>
#include <random>
#define ll long long
// #define int long long
#define fi first
#define se second
#define pb push_back
#define md ((l+r)>>1)
#define lf (id<<1)
#define rg ((id<<1)|1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 3e5+10;
const int MAXA = 1e6+10;
const int INF = 1e9;
const int LOG = 30;
const int MOD = 1e9+7;

int n;

struct node {
	int val, laz, l, r;
	node *le, *ri;
	void bd(int l2, int r2){
		val = 0; laz = 0;
		l = l2; r = r2;
		if(l==r) return;
		le = NULL; ri = NULL;
	}
	void bnc(){
		if(le==NULL){
			le = new node(); 
			le->l = l; le->r = md;
			le->bd(l, md);
		}
		if(ri==NULL){
			ri = new node(); 
			ri->l = md+1; ri->r = r;
			ri->bd(md+1, r);
		}
		if(laz == 0) return;
		le->val = (le->r-le->l+1) * laz; le->laz |= laz;
		ri->val = (ri->r-ri->l+1) * laz; ri->laz |= laz;
		laz = 0;
	}
	int que(int x, int y){
		if(x<=l && r<=y) return val;
		if(r<x || y<l) return 0;
		bnc();
		return le->que(x, y) + ri->que(x, y);
	}
	int upd(int x, int y, int p){
		if(x<=l && r<=y){
			laz |= p;
			return val = (r-l+1) * p;
		}
		if(r<x || y<l) return val;
		bnc();
		return val = le->upd(x, y, 1) + ri->upd(x, y, 1);
	}
} A;

signed main() {
	// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	A.bd(1, INF); int c = 0;
	for(int i=1; i<=n; i++){
		int ty, x, y; cin >> ty >> x >> y;
		x += c; y += c;
		if(ty==2) A.upd(x, y, 1);
		else {
			int ans = A.que(x, y);
			cout << ans << '\n';
			c = ans;
		}
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	20 ms	5116 KB	Output is correct
5	Correct	23 ms	5980 KB	Output is correct
6	Correct	22 ms	5724 KB	Output is correct
7	Correct	22 ms	5980 KB	Output is correct
8	Correct	174 ms	44712 KB	Output is correct
9	Correct	309 ms	77392 KB	Output is correct
10	Correct	317 ms	85324 KB	Output is correct
11	Correct	323 ms	91660 KB	Output is correct
12	Correct	352 ms	94620 KB	Output is correct
13	Correct	321 ms	110064 KB	Output is correct
14	Correct	340 ms	110984 KB	Output is correct
15	Correct	498 ms	202084 KB	Output is correct
16	Correct	443 ms	203368 KB	Output is correct
17	Correct	311 ms	114944 KB	Output is correct
18	Correct	373 ms	114768 KB	Output is correct
19	Correct	497 ms	207768 KB	Output is correct
20	Correct	535 ms	207808 KB	Output is correct