Submission #338850

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338850	2020-12-24T05:07:42 Z	tengiz05	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	627 ms	206060 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, 1000000000000000ll);
			cout << res << '\n';
			lastans = res;
		}else {
			// update
			update(root, l+lastans, r+lastans, 1, 1000000000000000ll);
		}
	}
	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	384 KB	Output is correct
4	Correct	23 ms	4900 KB	Output is correct
5	Correct	26 ms	5996 KB	Output is correct
6	Correct	25 ms	5760 KB	Output is correct
7	Correct	28 ms	5868 KB	Output is correct
8	Correct	195 ms	44012 KB	Output is correct
9	Correct	416 ms	76012 KB	Output is correct
10	Correct	434 ms	84256 KB	Output is correct
11	Correct	433 ms	90220 KB	Output is correct
12	Correct	436 ms	93292 KB	Output is correct
13	Correct	395 ms	108140 KB	Output is correct
14	Correct	399 ms	109292 KB	Output is correct
15	Correct	607 ms	200044 KB	Output is correct
16	Correct	600 ms	201452 KB	Output is correct
17	Correct	406 ms	113188 KB	Output is correct
18	Correct	413 ms	112976 KB	Output is correct
19	Correct	609 ms	205804 KB	Output is correct
20	Correct	627 ms	206060 KB	Output is correct