답안 #96065

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
96065 2019-02-05T15:40:32 Z Shafin666 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
635 ms 170124 KB
#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;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 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