oj.uz

답안 #899905

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
899905 2024-01-07T09:23:55 Z PotatoMan 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
 255 ms 201872 KB 
#include <bits/stdc++.h>
#define inf INT_MAX
#define longlonginf LONG_LONG_MAX
#define mod 1000000007
#define MAXN 100005
#define pii pair<ll,ll>
#define ll long long
#define deb(x) cerr<<"[ "<<#x<<" = "<<x<<" ]";
#define yes() cout<<"YES\n";
#define no() cout<<"NO\n";
using namespace std;
 
ll n,k,m,cur,z,q;
ll ans = 0;
string subtask;

struct node{
	int val,lazy,lc = -1,rc = -1,tl,tr;
	node(int pl,int pr){
		val = 0,lazy = 0,tl = pl, tr = pr, lc = -1,rc = -1;
	}
	void checklazy(int x){
		if(!x) return;
		val = tr-tl+1;
		lazy = x;
	}
};

struct segment_tree{
	vector<node> v;
	segment_tree(){
		v.push_back(node(1,1e9));
	}
	void prop(int x){
		if( v[x].tl != v[x].tr ){
			v[x].checklazy(v[x].lazy);
			int m = (v[x].tl+v[x].tr)/2;
			if(v[x].lc == -1){
				v[x].lc = v.size();
				v.push_back(node(v[x].tl,m));
			}
			if(v[x].rc == -1){
				v[x].rc = v.size();
				v.push_back(node(m+1,v[x].tr));
			}
			v[v[x].lc].checklazy(v[x].lazy);
			v[v[x].rc].checklazy(v[x].lazy);
			v[x].lazy = 0;
		}
	}
	void update(int l,int r,int x){
		if( l > v[x].tr || r < v[x].tl ) return;
		if( l <= v[x].tl && v[x].tr <= r ){
			v[x].checklazy(1);
			return;
		}
		prop(x);
		update(l,r,v[x].lc);
		update(l,r,v[x].rc);
		v[x].val = v[v[x].lc].val + v[v[x].rc].val;
	}
	int query(int l,int r,int x){
		if( l > v[x].tr || r < v[x].tl ) return 0;
		if( l <= v[x].tl && v[x].tr <= r ) {
			v[x].checklazy(v[x].lazy);
			return v[x].val;
		}
		prop(x);
		return query(l,r,v[x].lc)+query(l,r,v[x].rc);
	}
};

void solve(){
	cin>>n;
	segment_tree seg;
	cur = 0;
	while(n--){
		ll x,y,z;
		cin>>x>>y>>z;
		if( x == 1 ){
			ll k = seg.query(y+cur,z+cur,0);
			cout<<k<<"\n";
			cur = k;
		}
		else{
			seg.update(y+cur,z+cur,0);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	//cin>>T;
	for(int i = 0 ; i < T ; i++){
		//cout<<"Case #"<<i+1<<": ";
		solve();
	}
	return 0;
}
 
/*
	misread -> missed subtask
	you thought u declared it huh?
	not i but x
	logical operator
	wrong example/proof
	thoroughly
	wrong variables
	thinking it wrong
	bruh just try some test case
	capitals ;-;
	wrong data structure lol
	count memory usement
	corner case
	oversized array
	orders
	statements
	size initializer
	while con
	map -> array
	wrong digits??
	swapped variables??
	check if theres any variabled
	that got declared twice
	find some pattern
	name collision
	constraints??!
	mod !!
	resets
*/

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 11 ms 3644 KB Output is correct
5 Correct 12 ms 3792 KB Output is correct
6 Correct 12 ms 3820 KB Output is correct
7 Correct 12 ms 5072 KB Output is correct
8 Correct 76 ms 26036 KB Output is correct
9 Correct 169 ms 51872 KB Output is correct
10 Correct 163 ms 52388 KB Output is correct
11 Correct 172 ms 52896 KB Output is correct
12 Correct 175 ms 51724 KB Output is correct
13 Correct 168 ms 103068 KB Output is correct
14 Correct 157 ms 102628 KB Output is correct
15 Correct 250 ms 200828 KB Output is correct
16 Correct 242 ms 201872 KB Output is correct
17 Correct 164 ms 103068 KB Output is correct
18 Correct 167 ms 102884 KB Output is correct
19 Correct 255 ms 201312 KB Output is correct
20 Correct 240 ms 201840 KB Output is correct