답안 #426575

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
426575 2021-06-14T07:01:10 Z CSQ31 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
521 ms 207824 KB
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
struct node{
	int lf,rg,sum,lazy;
	node *l,*r;
	node(int _lf,int _rg){
		l = nullptr;
		r = nullptr;
		sum = lazy = 0;
		lf = _lf;
		rg = _rg;
	}
	void pushdown(){
		int tm = (lf+rg)/2;
		if(l == nullptr)l = new node(lf,tm);
		if(r == nullptr)r = new node(tm+1,rg);
		if(lazy){
			lazy = 0;
			l->lazy = r->lazy = 1;
			l->sum = tm-lf+1;
			r->sum = rg-tm;
		}
	}
	void upd(int L,int R){
		if(L == lf && rg == R){
			sum = rg-lf+1;
			lazy = 1;
			return;
		}
		pushdown();
		int tm = (lf+rg)/2;
		if(R<=tm)l->upd(L,R);
		else if(tm<L)r->upd(L,R);
		else{
			l->upd(L,tm);
			r->upd(tm+1,R);
		}
		sum = l->sum + r->sum;
	}
	int query(int L,int R){
		if(L == lf && rg == R){
			return sum;
		}
		int tm = (lf+rg)/2;
		pushdown();
		if(R<=tm)return l->query(L,R);
		else if(tm<L)return r->query(L,R);
		else return l->query(L,tm) + r->query(tm+1,R);
	}
}*root = new node(1,1e9);
int main(){
	owo
	int m;
	cin>>m;
	int c=0;
	while(m--){
		int d,x,y;
		cin>>d>>x>>y;
		if(d==1){
			c = root->query(x+c,y+c);
			cout<<c<<'\n';	
		}else{
			root->upd(x+c,y+c);
		}
	}
	
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 14 ms 4968 KB Output is correct
5 Correct 19 ms 6052 KB Output is correct
6 Correct 17 ms 5800 KB Output is correct
7 Correct 18 ms 5964 KB Output is correct
8 Correct 153 ms 44472 KB Output is correct
9 Correct 308 ms 77248 KB Output is correct
10 Correct 316 ms 85424 KB Output is correct
11 Correct 334 ms 91664 KB Output is correct
12 Correct 321 ms 94500 KB Output is correct
13 Correct 336 ms 109900 KB Output is correct
14 Correct 278 ms 111064 KB Output is correct
15 Correct 457 ms 201796 KB Output is correct
16 Correct 430 ms 203144 KB Output is correct
17 Correct 302 ms 114992 KB Output is correct
18 Correct 286 ms 114812 KB Output is correct
19 Correct 471 ms 207824 KB Output is correct
20 Correct 521 ms 207660 KB Output is correct