Submission #338833

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338833	2020-12-24T04:37:16 Z	tengiz05	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	534 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 l, r, ans, pr;
	array<node*, 2> kids;
	node(int l, int r){
		kids = {NULL, NULL};
		this->l = l;
		this->r = r;
		ans = pr = 0;
	}
};
void prop(node *root){
	if(root->pr){
		for(auto to : root->kids)if(to != NULL)to->pr |= root->pr;
		int len = (root->r - root->l+1);
		root->ans = len;
	}
}
void update(node *root, int l, int r){
	int mid = (root->l+root->r)/2;
	if(root->kids[0] == NULL)root->kids[0] = new node(root->l, mid);
	if(root->kids[1] == NULL)root->kids[1] = new node(mid+1, root->r);
	prop(root);
	if(root->l > r || root->r < l)return;
	if(root->l >= l && root->r <= r){
		root->pr = 1;
	//	cout << root->l << ' ' << root->r << '\n';
		prop(root);
		return;
	}update(root->kids[0], l, r);
	update(root->kids[1], l, r);
	root->ans = 0;
	for(auto to : root->kids)root->ans += to->ans;
}
int query(node *root, int l, int r){
	int mid = (root->l+root->r)/2;
	if(root->kids[0] == NULL)root->kids[0] = new node(root->l, mid);
	if(root->kids[1] == NULL)root->kids[1] = new node(mid+1, root->r);
	prop(root);
	if(root->l > r || root->r < l)return 0;
	if(root->l >= l && root->r <= r){
	//	cout << root->l << ' ' << root->r << '\n';
		return root->ans;
	}int res = 0;
	res += query(root->kids[0], l, r);
	res += query(root->kids[1], l, r);
	return res;
}
void solve(int test_case){
	int i, j, q;
	cin >> q;
	int lastans = 0;
	node *root = new node(1, mod);
	while(q--){
		int type;
		cin >> type;
		int l, r;
		cin >> l >> r;
		if(type == 1){
			// query
			int res = query(root, l+lastans, r+lastans);
			cout << res << '\n';
			lastans = res;
		}else {
			// update
			update(root, l+lastans, r+lastans);
		}
	}
	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:65:6: warning: unused variable 'i' [-Wunused-variable]
   65 |  int i, j, q;
      |      ^
apple.cpp:65:9: warning: unused variable 'j' [-Wunused-variable]
   65 |  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	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	24 ms	9452 KB	Output is correct
5	Correct	29 ms	11500 KB	Output is correct
6	Correct	28 ms	11116 KB	Output is correct
7	Correct	29 ms	11500 KB	Output is correct
8	Correct	232 ms	87020 KB	Output is correct
9	Correct	476 ms	150552 KB	Output is correct
10	Correct	514 ms	166636 KB	Output is correct
11	Correct	508 ms	180972 KB	Output is correct
12	Correct	515 ms	186604 KB	Output is correct
13	Correct	534 ms	217560 KB	Output is correct
14	Correct	482 ms	219372 KB	Output is correct
15	Runtime error	504 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Halted	0 ms	0 KB	-