oj.uz

답안 #630220

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
630220 2022-08-16T05:58:07 Z zhangjishen 원숭이와 사과 나무 (IZhO12_apple) C++
100 / 100
 329 ms 105304 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 1e9, MAXQ = 1e5 + 10;

// explicit segment tree
struct Node{
	int l, r;
	int sum, tag;
	int ls, rs;	
}t[MAXQ * 30 * 4];
int tot, root;

int newn(int l, int r){	// allocate memory for node [l, r]
	++tot;
	t[tot].l = l; t[tot].r = r;
	t[tot].sum = t[tot].tag = 0;
	t[tot].ls = t[tot].rs = 0;
	return tot;
}

void pushup(int u){
	t[u].sum = t[t[u].ls].sum + t[t[u].rs].sum;
}

void pushdown(int u){
	if(t[u].tag){
		int mid = (t[u].l + t[u].r) / 2;
		if(!t[u].ls) t[u].ls = newn(t[u].l, mid);
		t[t[u].ls].sum = mid - t[u].l + 1;
		t[t[u].ls].tag = 1;
		if(!t[u].rs) t[u].rs = newn(mid + 1, t[u].r);
		t[t[u].rs].sum = t[u].r - mid;
		t[t[u].rs].tag = 1;
		t[u].tag = 0;
	}
}

void update(int u, int ul, int ur){	// cover [ul, ur] in [l, r] with 1
	if(t[u].l == ul && t[u].r == ur){
		t[u].sum = (t[u].r - t[u].l + 1);
		t[u].tag = 1;
		return;
	}
	int mid = (t[u].l + t[u].r) / 2;
	pushdown(u);
	if(ul <= mid){
		if(!t[u].ls) t[u].ls = newn(t[u].l, mid);
		update(t[u].ls, ul, min(ur, mid));
	}
	if(ur >= mid + 1){
		if(!t[u].rs) t[u].rs = newn(mid + 1, t[u].r);
		update(t[u].rs, max(ul, mid + 1), ur);
	}
	pushup(u);
}

int query(int u, int ql, int qr){	// query sum of [ql, qr] in [l, r]
	if(t[u].l == ql && t[u].r == qr)
		return t[u].sum;
	int mid = (t[u].l + t[u].r) / 2, L = 0, R = 0;
	pushdown(u);
	if(ql <= mid && t[u].ls)
		L = query(t[u].ls, ql, min(qr, mid));
	if(qr >= mid + 1 && t[u].rs)
		R = query(t[u].rs, max(ql, mid + 1), qr);
	return L + R;
}

int m;
int main(){
	// biuld segment tree
	tot = 0;
	root = newn(1, N);
	// operations
	scanf("%d", &m);
	int op, l, r, c = 0;
	for(int i = 1; i <= m; i++){
		scanf("%d %d %d", &op, &l, &r);
		l += c; r += c;
		if(op == 1){
			c = query(root, l, r);
			printf("%d\n", c);
		}else update(root, l, r);
	}
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%d", &m);
      |  ~~~~~^~~~~~~~~~
apple.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   scanf("%d %d %d", &op, &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 12 ms 2644 KB Output is correct
5 Correct 14 ms 3156 KB Output is correct
6 Correct 14 ms 3164 KB Output is correct
7 Correct 14 ms 3216 KB Output is correct
8 Correct 107 ms 22872 KB Output is correct
9 Correct 218 ms 39768 KB Output is correct
10 Correct 221 ms 43884 KB Output is correct
11 Correct 234 ms 47048 KB Output is correct
12 Correct 241 ms 48404 KB Output is correct
13 Correct 209 ms 56320 KB Output is correct
14 Correct 202 ms 56908 KB Output is correct
15 Correct 316 ms 102336 KB Output is correct
16 Correct 262 ms 102952 KB Output is correct
17 Correct 218 ms 58772 KB Output is correct
18 Correct 210 ms 58860 KB Output is correct
19 Correct 329 ms 105296 KB Output is correct
20 Correct 306 ms 105304 KB Output is correct