Submission #885939

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
885939	2023-12-11T07:34:25 Z	dosts	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	283 ms	163668 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;
	inline Node(int a,int b) {
		c[0] = c[1] = NULL;
		l = a;
		r = b;
	}
	inline void apply() {
		if (lazy) sum = r-l+1;
	}
	inline 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);
	}
	inline void push() {
		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;
			apply();
			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	600 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	12 ms	4008 KB	Output is correct
5	Correct	15 ms	4984 KB	Output is correct
6	Correct	15 ms	4956 KB	Output is correct
7	Correct	15 ms	4892 KB	Output is correct
8	Correct	94 ms	37204 KB	Output is correct
9	Correct	192 ms	65616 KB	Output is correct
10	Correct	199 ms	72272 KB	Output is correct
11	Correct	203 ms	76884 KB	Output is correct
12	Correct	202 ms	79000 KB	Output is correct
13	Correct	197 ms	85336 KB	Output is correct
14	Correct	202 ms	87276 KB	Output is correct
15	Correct	283 ms	160248 KB	Output is correct
16	Correct	283 ms	160596 KB	Output is correct
17	Correct	195 ms	90204 KB	Output is correct
18	Correct	202 ms	90220 KB	Output is correct
19	Correct	278 ms	163664 KB	Output is correct
20	Correct	280 ms	163668 KB	Output is correct