Submission #96065

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
96065	2019-02-05T15:40:32 Z	Shafin666	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	635 ms	170124 KB

apple

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define to second
#define cost first
typedef long long ll;
typedef long double ld;
using namespace std;

struct Node {
	int sum, lazy;
	Node *l, *r;
	Node() : sum(0), lazy(0), l(NULL), r(NULL) { }
}; Node *root;

void propagate(Node *v, int len) {
	if(v->lazy) {
		if(v->l == NULL) v->l = new Node;
		v->l->sum = len/2;
		v->l->lazy = 1;

		if(v->r == NULL) v->r = new Node;
		v->r->sum = len/2;
		v->r->lazy = 1;

		v->sum = len;
		v->lazy = 0;
	}
}

void add(Node *v, int L, int R, int l, int r) {
	if(L >= l && R <= r) { 
		v->sum =  (R-L+1); 
		v->lazy = 1;
		return; 
	}
	propagate(v, R-L+1);

	int mid = (L+R)/2;

	if(l <= mid) {
		if(v->l == NULL) v->l = new Node;
		add(v->l, L, mid, l, min(r, mid));
	}
	if(mid < r) {
		if(v->r == NULL) v->r = new Node;
		add(v->r, mid+1, R, max(l, mid+1), r);
	}

	v->sum = 0;
	if(v->l != NULL) v->sum += v->l->sum;
	if(v->r != NULL) v->sum += v->r->sum;
}

int get(Node *v, int L, int R, int l, int r) {
	if(v == NULL) return 0;

	int mid = (L+R)/2;
	int ans = 0;

	propagate(v, R-L+1);
	if(L >= l && R <= r) return v->sum;
	if(l <= mid) ans += get(v->l, L, mid, l, min(mid, r));
	if(mid < r) ans += get(v->r, mid+1, R, max(mid+1, l), r);

	return ans;
}

void update(int x, int y) { add(root, 1, (1<<30), x, y); }
int query(int x, int y) { return get(root, 1, (1<<30), x, y); }

int main()
{
	int n, c = 0;
	int x, l, r;

	root = new Node;

	scanf("%d", &n); //cin >> n;
	while(n--) {
		scanf("%d%d%d", &x, &l, &r); //cin >> x >> l >> r;
		l += c; r += c;

		if(x == 2) update(l, r);
		else {
			c = query(l, r);
			//c += ans;
			cout << c << endl;
		}
	}
    return 0;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n); //cin >> n;
  ~~~~~^~~~~~~~~~
apple.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &x, &l, &r); //cin >> x >> l >> r;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	23 ms	4088 KB	Output is correct
5	Correct	26 ms	4984 KB	Output is correct
6	Correct	27 ms	4796 KB	Output is correct
7	Correct	27 ms	4984 KB	Output is correct
8	Correct	231 ms	36128 KB	Output is correct
9	Correct	407 ms	65524 KB	Output is correct
10	Correct	424 ms	69240 KB	Output is correct
11	Correct	450 ms	74360 KB	Output is correct
12	Correct	440 ms	76536 KB	Output is correct
13	Correct	402 ms	90664 KB	Output is correct
14	Correct	423 ms	91228 KB	Output is correct
15	Correct	613 ms	164796 KB	Output is correct
16	Correct	635 ms	166044 KB	Output is correct
17	Correct	392 ms	94280 KB	Output is correct
18	Correct	400 ms	94172 KB	Output is correct
19	Correct	597 ms	169888 KB	Output is correct
20	Correct	567 ms	170124 KB	Output is correct