답안 #969361

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
969361 2024-04-25T03:40:29 Z tamir1 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
366 ms 262144 KB
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll m,i,x,y,d,c,ans;
struct node{
	node *le,*ri;
	ll val,lazy,l,r;
};
void fix(node *&s){          
	if(s->l==s->r){
		if(s->lazy==1) s->val=1;
		return;
	}
	ll mid=(s->l+s->r)/2;
	if(s->le==NULL){
		s->le=new node;
		s->le->le=NULL;
		s->le->ri=NULL;
		s->le->l=s->l;
		s->le->r=mid;
		s->le->lazy=0;
		s->le->val=0;
	}
	if(s->ri==NULL){
		s->ri=new node;
		s->ri->le=NULL;
		s->ri->ri=NULL;
		s->ri->l=mid+1;
		s->ri->r=s->r;
		s->ri->lazy=0;
		s->ri->val=0;
	}
	if(s->lazy==1){
		s->val=s->r-s->l+1;
		s->le->lazy=1;
		s->ri->lazy=1;
		s->lazy=0;
	}
}
ll query(node *&s,ll x,ll y){
	fix(s);
	if(s->l>y || s->r<x) return 0;
	if(s->l>=x && s->r<=y) return s->val;
	return query(s->le,x,y)+query(s->ri,x,y);
}
void update(node *&s,ll x,ll y){
	fix(s);
	if(s->l>y || s->r<x) return;
	if(s->l>=x && s->r<=y){
		s->val=s->r-s->l+1;
		if(s->l!=s->r){
			s->le->lazy=1;
			s->ri->lazy=1;
		}
		return;
	}
	update(s->le,x,y);
	update(s->ri,x,y);
	s->val=s->le->val+s->ri->val;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> m;
	node *s = new node;
	s->le=NULL;
	s->ri=NULL;
	s->val=0;
	s->lazy=0;
	s->l=1;
	s->r=1e9;
	for(i=1;i<=m;i++){
		cin >> d >> x >> y;
		if(d==1){
			ans=query(s,x+c,y+c);
			cout << ans << "\n";
			c=ans;
		}
		else{
			update(s,x+c,y+c);
		}
	}
}
# 결과 실행 시간 메모리 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 16 ms 11292 KB Output is correct
5 Correct 19 ms 13872 KB Output is correct
6 Correct 19 ms 13144 KB Output is correct
7 Correct 19 ms 13660 KB Output is correct
8 Correct 167 ms 102580 KB Output is correct
9 Correct 319 ms 174164 KB Output is correct
10 Correct 351 ms 195920 KB Output is correct
11 Correct 359 ms 212560 KB Output is correct
12 Correct 366 ms 220020 KB Output is correct
13 Runtime error 326 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -