답안 #969360

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
969360 2024-04-25T03:39:05 Z tamir1 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
360 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 15 ms 11612 KB Output is correct
5 Correct 19 ms 14028 KB Output is correct
6 Correct 19 ms 13396 KB Output is correct
7 Correct 19 ms 13916 KB Output is correct
8 Correct 174 ms 103308 KB Output is correct
9 Correct 320 ms 176084 KB Output is correct
10 Correct 334 ms 197444 KB Output is correct
11 Correct 354 ms 214024 KB Output is correct
12 Correct 360 ms 221344 KB Output is correct
13 Runtime error 331 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -