oj.uz

답안 #333032

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
333032 2020-12-04T09:30:28 Z nandonathaniel 원숭이와 사과 나무 (IZhO12_apple) C++14
0 / 100
 265 ms 95980 KB 
#include<bits/stdc++.h>
using namespace std;

int tree[3000005],lazy[3000005],ki[3000005],ka[3000005],node=2;

void pushdown(int now,int L,int R){
	int mid=(L+R)/2;
	if(ki[now]==0){
		ki[now]=node;
		node++;
	}
	if(ka[now]==0){
		ka[now]=node;
		node++;
	}
	tree[ki[now]]=mid-L+1;
	lazy[ki[now]]=1;
	tree[ka[now]]=R-mid;
	lazy[ka[now]]=1;
	lazy[now]=0;
}

void update(int now,int L,int R,int x,int y){
    //if(tree[now]==R-L+1)return;
	if(L>=x && R<=y){
		tree[now]=R-L+1;
		lazy[now]=1;
		return;
	}
	if(L>y || R<x)return;
	int mid=(L+R)/2;
	if(lazy[now])pushdown(now,L,R);
	if(ki[now]==0){
		ki[now]=node;
		node++;
	}
	if(ka[now]==0){
		ka[now]=node;
		node++;
	}
	update(ki[now],L,mid,x,y);
	update(ka[now],mid+1,R,x,y);
	tree[now]=tree[ki[now]]+tree[ka[now]];
}

int query(int now,int L,int R,int x,int y){
	if(L>=x && R<=y){
		return tree[now];
	}
	if(L>y || R<x || now==0)return 0;
	if(lazy[now])pushdown(now,L,R);
	int mid=(L+R)/2;
	return query(ki[now],L,mid,x,y)+query(ka[now],mid+1,R,x,y);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int q,op,x,y,c=0;
	cin >> q;
	while(q--){
		cin >> op >> x >> y;
		x+=c;
		y+=c;
		if(op==1){
			c=query(1,1,1e9,x,y);
			cout << c << '\n';
		}
		else update(1,1,1e9,x,y);
	}
	return 0;
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 11 ms 1900 KB Output is correct
5 Correct 13 ms 2284 KB Output is correct
6 Correct 13 ms 2156 KB Output is correct
7 Correct 14 ms 2284 KB Output is correct
8 Correct 108 ms 15084 KB Output is correct
9 Correct 235 ms 25708 KB Output is correct
10 Correct 242 ms 28652 KB Output is correct
11 Correct 242 ms 30572 KB Output is correct
12 Correct 243 ms 31468 KB Output is correct
13 Correct 210 ms 36716 KB Output is correct
14 Correct 207 ms 36972 KB Output is correct
15 Runtime error 265 ms 95980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -