답안 #338834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
338834	2020-12-24T04:42:02 Z	tengiz05	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	698 ms	262148 KB

apple

#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 a[N], n, m, k;
struct node{
	int ans, 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;
	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);
	if(L > r || R < l)return;
	if(L >= l && R <= r){
		root->pr = 1;
	//	cout << root->l << ' ' << root->r << '\n';
		prop(root, R-L+1);
		return;
	}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;
	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);
	if(L > r || R < l)return 0;
	if(L >= l && R <= r){
	//	cout << root->l << ' ' << root->r << '\n';
		return root->ans;
	}int res = 0;
	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, mod);
			cout << res << '\n';
			lastans = res;
		}else {
			// update
			update(root, l+lastans, r+lastans, 1, mod);
		}
	}
	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:62:6: warning: unused variable 'i' [-Wunused-variable]
   62 |  int i, j, q;
      |      ^
apple.cpp:62:9: warning: unused variable 'j' [-Wunused-variable]
   62 |  int i, j, q;
      |         ^

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	24 ms	6380 KB	Output is correct
5	Correct	35 ms	7788 KB	Output is correct
6	Correct	26 ms	7660 KB	Output is correct
7	Correct	33 ms	7788 KB	Output is correct
8	Correct	217 ms	58348 KB	Output is correct
9	Correct	412 ms	100588 KB	Output is correct
10	Correct	450 ms	111468 KB	Output is correct
11	Correct	455 ms	119820 KB	Output is correct
12	Correct	500 ms	123540 KB	Output is correct
13	Correct	431 ms	143860 KB	Output is correct
14	Correct	437 ms	145132 KB	Output is correct
15	Runtime error	698 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Halted	0 ms	0 KB	-