Submission #338851

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338851	2020-12-24T05:08:08 Z	tengiz05	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	632 ms	206288 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 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, 1000000000000000000ll);
			cout << res << '\n';
			lastans = res;
		}else {
			// update
			update(root, l+lastans, r+lastans, 1, 1000000000000000000ll);
		}
	}
	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(long long 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

#	Verdict	Execution time	Memory	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	21 ms	4972 KB	Output is correct
5	Correct	32 ms	5868 KB	Output is correct
6	Correct	27 ms	5740 KB	Output is correct
7	Correct	29 ms	5868 KB	Output is correct
8	Correct	205 ms	43884 KB	Output is correct
9	Correct	435 ms	76012 KB	Output is correct
10	Correct	444 ms	84332 KB	Output is correct
11	Correct	469 ms	90348 KB	Output is correct
12	Correct	456 ms	93276 KB	Output is correct
13	Correct	414 ms	108220 KB	Output is correct
14	Correct	413 ms	109292 KB	Output is correct
15	Correct	623 ms	200428 KB	Output is correct
16	Correct	620 ms	201580 KB	Output is correct
17	Correct	422 ms	113260 KB	Output is correct
18	Correct	425 ms	113132 KB	Output is correct
19	Correct	632 ms	206196 KB	Output is correct
20	Correct	626 ms	206288 KB	Output is correct