Submission #885934

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
885934	2023-12-11T07:24:58 Z	dosts	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	481 ms	255512 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;
		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	1 ms	348 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	15 ms	5824 KB	Output is correct
5	Correct	19 ms	6988 KB	Output is correct
6	Correct	24 ms	6788 KB	Output is correct
7	Correct	24 ms	7000 KB	Output is correct
8	Correct	139 ms	52876 KB	Output is correct
9	Correct	284 ms	91024 KB	Output is correct
10	Correct	324 ms	101216 KB	Output is correct
11	Correct	335 ms	108860 KB	Output is correct
12	Correct	309 ms	112472 KB	Output is correct
13	Correct	292 ms	132872 KB	Output is correct
14	Correct	288 ms	134552 KB	Output is correct
15	Correct	474 ms	248404 KB	Output is correct
16	Correct	481 ms	249680 KB	Output is correct
17	Correct	292 ms	141324 KB	Output is correct
18	Correct	279 ms	141340 KB	Output is correct
19	Correct	470 ms	255512 KB	Output is correct
20	Correct	479 ms	255496 KB	Output is correct