Submission #885937

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
885937	2023-12-11T07:31:16 Z	dosts	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	301 ms	163752 KB

apple

#include <bits/stdc++.h>
#pragma GCC optimize "O3,unroll-loops"
using namespace std;
#define sp << " " << 
//#define int long long
#define vi vector<int>
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>
#define pb push_back
const int N = 2e5+1;
 
 
struct Node {
	Node* c[2];
	int sum = 0,l,r;
	bool lazy = 0;
	Node(int a,int b) {
		c[0] = c[1] = NULL;
		l = a;
		r = b;
	}
	void apply() {
		if (lazy) sum = r-l+1;
	}
	void extend() {
		int m = (l+r) >> 1;
		if (c[0]==NULL) c[0] = new Node(l,m);
		if (c[1]==NULL) c[1] = new Node(m+1,r);
	}
	void push() {
		apply();
		if (l^r) {
			extend();
			c[0]->lazy |= lazy;
			c[1]->lazy |= lazy;
		}
	}
 
	void upd(int L,int R) {
		apply();
		if (l > R ||  r < L) return;
		if (l >= L && r <= R) {
			lazy = 1;
			push();
			return;
		}
		push();
		int m = (l+r) >> 1;
		c[0]->upd(L,R),c[1]->upd(L,R);
		sum = c[0]->sum+c[1]->sum;
	}
 
	int query(int L,int R) {
		apply();
		if (l > R || r < L) return 0;
		if (l >= L && r <= R) return sum;
		if(lazy){
			if (L >= l && R <= r) return R-L+1;
			else if (L <= l) return R-l+1;
			else return r-L+1;
		}
		push();
		return c[0]->query(L,R)+c[1]->query(L,R);
	}
 
};
 
void solve() {
	int q;
	cin >> q;
	int c = 0;
	Node* root = new Node(1,1e9);
	while (q--) {
		int t,l,r;
		cin >> t >> l >> r;
		if (t == 1) {
			c = root->query(l+c,r+c);
			cout << c << endl;
		}
		else root->upd(l+c,r+c);
	}
 
}
    
                  
                             
signed main() { 
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  #ifdef Local
  freopen("in","r",stdin);
  freopen("out","w",stdout); 
  #endif
  int t = 1;
  //cin >> t;
	F(i,t) solve();
}

Compilation message

apple.cpp: In member function 'void Node::upd(int, int)':
apple.cpp:48:7: warning: unused variable 'm' [-Wunused-variable]
   48 |   int m = (l+r) >> 1;
      |       ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	600 KB	Output is correct
4	Correct	12 ms	4020 KB	Output is correct
5	Correct	21 ms	5212 KB	Output is correct
6	Correct	15 ms	4760 KB	Output is correct
7	Correct	15 ms	4952 KB	Output is correct
8	Correct	94 ms	37208 KB	Output is correct
9	Correct	216 ms	65736 KB	Output is correct
10	Correct	200 ms	72280 KB	Output is correct
11	Correct	203 ms	76824 KB	Output is correct
12	Correct	210 ms	79336 KB	Output is correct
13	Correct	204 ms	85160 KB	Output is correct
14	Correct	198 ms	87292 KB	Output is correct
15	Correct	282 ms	160104 KB	Output is correct
16	Correct	301 ms	160480 KB	Output is correct
17	Correct	189 ms	90304 KB	Output is correct
18	Correct	199 ms	90132 KB	Output is correct
19	Correct	281 ms	163488 KB	Output is correct
20	Correct	281 ms	163752 KB	Output is correct