Submission #630220

#	Time	Username	Problem	Language	Result	Execution time	Memory
630220		zhangjishen	Monkey and Apple-trees (IZhO12_apple)	C++98	100 / 100	329 ms	105304 KiB

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

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