Submission #885930

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
885930	2023-12-11T07:12:02 Z	dosts	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	411 ms	262144 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();
			int m = (l+r) >> 1;
			c[0]->lazy |= lazy;
			c[1]->lazy |= lazy;
		}
	}

	void upd(int L,int R) {
		push();
		if (l > R || r < L) return;
		if (l >= L && r <= R) {
			lazy = 1;
			push();
			return;
		}
		c[0]->upd(L,R),c[1]->upd(L,R);
		sum=c[0]->sum+c[1]->sum;
	}

	int query(int L,int R) {
		if (l > R || r < L) return 0;
		push();
		if (l >= L && r <= R) return sum;
		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::push()':
apple.cpp:34:8: warning: unused variable 'm' [-Wunused-variable]
   34 |    int m = (l+r) >> 1;
      |        ^

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	18 ms	7768 KB	Output is correct
5	Correct	21 ms	9424 KB	Output is correct
6	Correct	21 ms	9052 KB	Output is correct
7	Correct	22 ms	9304 KB	Output is correct
8	Correct	163 ms	69464 KB	Output is correct
9	Correct	326 ms	118612 KB	Output is correct
10	Correct	373 ms	132760 KB	Output is correct
11	Correct	352 ms	143568 KB	Output is correct
12	Correct	367 ms	148392 KB	Output is correct
13	Correct	361 ms	181140 KB	Output is correct
14	Correct	345 ms	183632 KB	Output is correct
15	Runtime error	411 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-