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

apple

#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){}
      |  ^~~~

Subtask #1

100.0 / 100.0

#	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