oj.uz

답안 #333038

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

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

void updatenode(int now,int L,int R){
	tree[now]=R-L+1;
	lazy[now]=1;
}

void pushdown(int now,int L,int R){
	if(lazy[now]==0)return;
	if(ki[now]==0){
		ki[now]=node;
		node++;
	}
	if(ka[now]==0){
		ka[now]=node;
		node++;
	}
	int mid=(L+R)/2;
	updatenode(ki[now],L,mid);
	updatenode(ka[now],mid+1,R);
	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){
		updatenode(now,L,R);
		return;
	}
	if(L>y || R<x)return;
	int mid=(L+R)/2;
	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;
	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
100.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 384 KB Output is correct
4 Correct 7 ms 1260 KB Output is correct
5 Correct 9 ms 1516 KB Output is correct
6 Correct 9 ms 1388 KB Output is correct
7 Correct 9 ms 1516 KB Output is correct
8 Correct 56 ms 9324 KB Output is correct
9 Correct 121 ms 16108 KB Output is correct
10 Correct 125 ms 17516 KB Output is correct
11 Correct 126 ms 18668 KB Output is correct
12 Correct 127 ms 19052 KB Output is correct
13 Correct 118 ms 20460 KB Output is correct
14 Correct 116 ms 20332 KB Output is correct
15 Correct 162 ms 37100 KB Output is correct
16 Correct 161 ms 37356 KB Output is correct
17 Correct 107 ms 20972 KB Output is correct
18 Correct 106 ms 21100 KB Output is correct
19 Correct 161 ms 38252 KB Output is correct
20 Correct 163 ms 38252 KB Output is correct