Submission #870645

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870645	2023-11-08T16:46:52 Z	NoLove	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	274 ms	188636 KB

apple

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;

struct Node {
	int sum, lazy, tl, tr, l, r;
	Node() : sum(0), lazy(0), l(-1), r(-1) {}
};

const int MAXN = 123456;
Node st[64 * MAXN];
int cnt = 2;

void push(int v) {
	if (st[v].lazy) {
		st[v].sum = st[v].tr - st[v].tl + 1;
		int mid = (st[v].tl + st[v].tr) / 2;
		if (st[v].l == -1) {
			st[v].l = cnt++;
			st[st[v].l].tl = st[v].tl;
			st[st[v].l].tr = mid;
		}
		if (st[v].r == -1) {
			st[v].r = cnt++;
			st[st[v].r].tl = mid + 1;
			st[st[v].r].tr = st[v].tr;
		}
		st[st[v].l].lazy = st[st[v].r].lazy = 1;
		st[v].lazy = 0;
	}
}

void upd(int v, int l, int r) {
	push(v);
	if (l == st[v].tl && r == st[v].tr) {
		st[v].lazy = 1;
		push(v);
	} else {
		int mid = (st[v].tl + st[v].tr) / 2;
		if (st[v].l == -1) {
			st[v].l = cnt++;
			st[st[v].l].tl = st[v].tl;
			st[st[v].l].tr = mid;
		}
		if (st[v].r == -1) {
			st[v].r = cnt++;
			st[st[v].r].tl = mid + 1;
			st[st[v].r].tr = st[v].tr;
		}

		if (l > mid) upd(st[v].r, l, r);
		else if (r <= mid) upd(st[v].l, l, r);
		else {
			upd(st[v].l, l, mid);
			upd(st[v].r, mid + 1, r);
		}

		push(st[v].l);
		push(st[v].r);
		st[v].sum =
		    st[st[v].l].sum + st[st[v].r].sum;
	}
}

int get(int v, int l, int r) {
	push(v);
	if (l == st[v].tl && r == st[v].tr)
		return st[v].sum;
	else {
		int mid = (st[v].tl + st[v].tr) / 2;
		if (st[v].l == -1) {
			st[v].l = cnt++;
			st[st[v].l].tl = st[v].tl;
			st[st[v].l].tr = mid;
		}
		if (st[v].r == -1) {
			st[v].r = cnt++;
			st[st[v].r].tl = mid + 1;
			st[st[v].r].tr = st[v].tr;
		}

		if (l > mid) return get(st[v].r, l, r);
		else if (r <= mid) return get(st[v].l, l, r);
		else
			return get(st[v].l, l, mid) +
			       get(st[v].r, mid + 1, r);
	}
}

int main() {
	iostream::sync_with_stdio(false);
    if (fopen("hi.inp", "r")) {
        freopen("hi.inp", "r", stdin);
//        freopen("hi.out", "w", stdout);
    } 
	cin.tie(0);
	int m;
	cin >> m;

	st[1].sum = 0;
	st[1].lazy = 0;
	st[1].tl = 1;
	st[1].tr = 1e9;

	int c = 0;
	FOR(_, 0, m) {
		int d, x, y;
		cin >> d >> x >> y;
		if (d == 1) {
			c = get(1, x + c, y + c);
			cout << c << '\n';
		} else upd(1, x + c, y + c);
	}
    
	return 0;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen("hi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	67 ms	185940 KB	Output is correct
2	Correct	41 ms	185932 KB	Output is correct
3	Correct	43 ms	185848 KB	Output is correct
4	Correct	51 ms	185936 KB	Output is correct
5	Correct	51 ms	186100 KB	Output is correct
6	Correct	42 ms	185936 KB	Output is correct
7	Correct	50 ms	185992 KB	Output is correct
8	Correct	113 ms	186948 KB	Output is correct
9	Correct	221 ms	187332 KB	Output is correct
10	Correct	208 ms	187256 KB	Output is correct
11	Correct	235 ms	187284 KB	Output is correct
12	Correct	238 ms	187216 KB	Output is correct
13	Correct	191 ms	187848 KB	Output is correct
14	Correct	194 ms	187744 KB	Output is correct
15	Correct	231 ms	188608 KB	Output is correct
16	Correct	241 ms	188604 KB	Output is correct
17	Correct	174 ms	188496 KB	Output is correct
18	Correct	182 ms	188500 KB	Output is correct
19	Correct	265 ms	188608 KB	Output is correct
20	Correct	274 ms	188636 KB	Output is correct