Submission #338835

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338835	2020-12-24T04:43:51 Z	tengiz05	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	710 ms	262144 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;
	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;
	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:63:6: warning: unused variable 'i' [-Wunused-variable]
   63 |  int i, j, q;
      |      ^
apple.cpp:63:9: warning: unused variable 'j' [-Wunused-variable]
   63 |  int i, j, q;
      |         ^

Subtask #1

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	6380 KB	Output is correct
5	Correct	26 ms	7788 KB	Output is correct
6	Correct	26 ms	7532 KB	Output is correct
7	Correct	26 ms	7788 KB	Output is correct
8	Correct	219 ms	58368 KB	Output is correct
9	Correct	425 ms	100588 KB	Output is correct
10	Correct	430 ms	111468 KB	Output is correct
11	Correct	448 ms	119660 KB	Output is correct
12	Correct	464 ms	123636 KB	Output is correct
13	Correct	430 ms	143852 KB	Output is correct
14	Correct	480 ms	145132 KB	Output is correct
15	Runtime error	710 ms	262144 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Halted	0 ms	0 KB	-