Submission #938973

# Submission time Handle Problem Language Result Execution time Memory
938973 2024-03-06T02:15:08 Z vjudge1 Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
506 ms 238156 KB
#include<bits/stdc++.h>
using namespace std;

struct node{
	int sum, l, r, lazy, ll, lr;
	node(): sum(0), lazy(0), l(-1), r(-1){}
};

node tr[10000000];
int temp=1;

void create(int now){
		int mid=(tr[now].ll+tr[now].lr)>>1;
		if (tr[now].l==-1){
			tr[now].l=temp;
			tr[temp].ll=tr[now].ll;
			tr[temp].lr=mid;
			temp++;
		}
		if (tr[now].r==-1){
			tr[now].r=temp;
			tr[temp].ll=mid+1;
			tr[temp].lr=tr[now].lr;
			temp++;
		}
}

void push(int now){
	create(now);
	if (tr[now].lazy){
		tr[now].sum=tr[now].lr-tr[now].ll+1;
		tr[tr[now].l].lazy=1;
		tr[tr[now].r].lazy=1;
		tr[now].lazy=0;
	}
}

void update(int now, int ql, int qr){
	int l=tr[now].ll, r=tr[now].lr;
	push(now);
	if (ql<=l and r<=qr){
		tr[now].lazy=1;
		push(now);
	} else{
		int mid=(tr[now].ll+tr[now].lr)>>1;
		int cl=tr[now].l, cr=tr[now].r;

		if (ql<=mid) update(cl, ql, qr);
		if (qr>mid) update(cr, ql, qr);

		push(cl);
		push(cr);
		tr[now].sum=tr[cl].sum+tr[cr].sum;
	}
}

int get(int now, int ql, int qr){
	int l=tr[now].ll, r=tr[now].lr;
	push(now);
	if (ql<=l and r<=qr){
		return tr[now].sum;
	} else{
		int mid=(tr[now].ll+tr[now].lr)>>1;
		int cl=tr[now].l, cr=tr[now].r;

		push(cl);
		push(cr);
		int a=0, b=0;
		if (ql<=mid) a=get(cl, ql, qr);
		if (qr>mid) b=get(cr, ql, qr);

		return a+b;
	}
}

int main(){
	int m;
	cin>>m;

	tr[0].sum=0;
	tr[0].ll=1;
	tr[0].lr=1e9;

	int c=0;

	while(m--){
		int d, x, y;
		cin>>d>>x>>y;
		if (d==1){
			c=get(0, x+c, y+c);
			cout<<c<<endl;
		} else{
			update(0, x+c, y+c);
		}
	}
	return 0;
}

Compilation message

apple.cpp: In constructor 'node::node()':
apple.cpp:5:17: warning: 'node::lazy' will be initialized after [-Wreorder]
    5 |  int sum, l, r, lazy, ll, lr;
      |                 ^~~~
apple.cpp:5:11: warning:   'int node::l' [-Wreorder]
    5 |  int sum, l, r, lazy, ll, lr;
      |           ^
apple.cpp:6:2: warning:   when initialized here [-Wreorder]
    6 |  node(): sum(0), lazy(0), l(-1), r(-1){}
      |  ^~~~
# Verdict Execution time Memory Grader output
1 Correct 83 ms 235088 KB Output is correct
2 Correct 79 ms 235100 KB Output is correct
3 Correct 82 ms 235088 KB Output is correct
4 Correct 100 ms 235252 KB Output is correct
5 Correct 102 ms 235344 KB Output is correct
6 Correct 109 ms 235332 KB Output is correct
7 Correct 100 ms 235348 KB Output is correct
8 Correct 214 ms 236320 KB Output is correct
9 Correct 359 ms 237172 KB Output is correct
10 Correct 383 ms 237252 KB Output is correct
11 Correct 359 ms 237316 KB Output is correct
12 Correct 396 ms 237396 KB Output is correct
13 Correct 346 ms 237804 KB Output is correct
14 Correct 408 ms 237568 KB Output is correct
15 Correct 413 ms 237932 KB Output is correct
16 Correct 415 ms 237864 KB Output is correct
17 Correct 352 ms 237604 KB Output is correct
18 Correct 368 ms 237648 KB Output is correct
19 Correct 418 ms 237908 KB Output is correct
20 Correct 506 ms 238156 KB Output is correct