Submission #630220

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
630220	2022-08-16T05:58:07 Z	zhangjishen	Monkey and Apple-trees (IZhO12_apple)	C++	100 / 100	329 ms	105304 KB

apple

#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

#	Verdict	Execution time	Memory	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