Submission #96065

#	Time	Username	Problem	Language	Result	Execution time	Memory
96065		Shafin666	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	635 ms	170124 KiB

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 (stderr)

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 / 100