oj.uz

답안 #338845

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
338845 2020-12-24T05:01:51 Z tengiz05 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 597 ms 139756 KB 
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool ckmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool ckmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 2e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int n, m, k;
struct node{
	int ans;
	bool pr;
	array<node*, 2> kids;
	node(){
		kids = {NULL, NULL};
		ans = pr = 0;
	}
};
void prop(node *root, int len){
	if(root->pr){
		for(auto to : root->kids)if(to != NULL)to->pr |= root->pr;
		root->ans = len;
	}
}
void update(node *root, int l, int r, int L, int R){
	int mid = (L+R)/2;
	prop(root, R-L+1);
	if(L > r || R < l)return;
	if(L >= l && R <= r){
		root->pr = 1;
		prop(root, R-L+1);
		return;
	}
	if(root->kids[0] == NULL)root->kids[0] = new node();
	if(root->kids[1] == NULL)root->kids[1] = new node();
	prop(root, R-L+1);
	update(root->kids[0], l, r, L, mid);
	update(root->kids[1], l, r, mid+1, R);
	root->ans = 0;
	for(auto to : root->kids)root->ans += to->ans;
}
int query(node *root, int l, int r, int L, int R){
	int mid = (L+R)/2;
	prop(root,R-L+1);
	if(L > r || R < l)return 0;
	if(L >= l && R <= r){
		return root->ans;
	}int res = 0;
	if(root->kids[0] == NULL)root->kids[0] = new node();
	if(root->kids[1] == NULL)root->kids[1] = new node();
	prop(root, R-L+1);
	res += query(root->kids[0], l, r, L, mid);
	res += query(root->kids[1], l, r, mid+1, R);
	return res;
}
void solve(int test_case){
	int i, j, q;
	cin >> q;
	int lastans = 0;
	node *root = new node();
	while(q--){
		int type;
		cin >> type;
		int l, r;
		cin >> l >> r;
		if(type == 1){
			// query
			int res = query(root, l+lastans, r+lastans, 1, 1000000000);
			cout << res << '\n';
			lastans = res;
		}else {
			// update
			update(root, l+lastans, r+lastans, 1, 1000000000);
		}
	}
	return;
}

signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int _T;
	cin >> _T;
	for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message

apple.cpp: In function 'void solve(int)':
apple.cpp:64:6: warning: unused variable 'i' [-Wunused-variable]
   64 |  int i, j, q;
      |      ^
apple.cpp:64:9: warning: unused variable 'j' [-Wunused-variable]
   64 |  int i, j, q;
      |         ^

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 364 KB Output is correct
4 Correct 17 ms 3436 KB Output is correct
5 Correct 21 ms 4076 KB Output is correct
6 Correct 21 ms 4076 KB Output is correct
7 Correct 29 ms 4076 KB Output is correct
8 Correct 175 ms 29420 KB Output is correct
9 Correct 351 ms 50676 KB Output is correct
10 Correct 381 ms 56044 KB Output is correct
11 Correct 390 ms 60268 KB Output is correct
12 Correct 386 ms 62188 KB Output is correct
13 Correct 351 ms 72300 KB Output is correct
14 Correct 352 ms 73068 KB Output is correct
15 Correct 526 ms 135532 KB Output is correct
16 Correct 570 ms 136532 KB Output is correct
17 Correct 386 ms 77548 KB Output is correct
18 Correct 381 ms 77568 KB Output is correct
19 Correct 597 ms 139660 KB Output is correct
20 Correct 542 ms 139756 KB Output is correct