Submission #525600

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
525600	2022-02-12T06:04:51 Z	shmad	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	369 ms	262148 KB

apple

#pragma GCC optimize("O3", "unroll-loops") // "Ofast"
#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt") 

#include <bits/stdc++.h>

#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vvi = vt< vt<int> >;

const int N = 1e6 + 5, mod = 1e9 + 7, inf = 1e18 + 7, B = 500, LIM = (1ll << 60), M = 1e9;
const double eps = 1e-6;

int n;

struct Node {
	int sum, tag;
	Node *l, *r;
	Node () : sum(0), tag(0), l(nullptr), r(nullptr) {}
};                       

void f (Node* &v) {
	if (!v) v = new Node();	
}

void push (Node* &v, int tl, int tr) {
	if (!v -> tag) return;
	v -> sum = (tr - tl + 1) * (v -> tag);
	if (tl != tr) {
		f(v -> l);
		f(v -> r);
		v -> l -> tag = v -> tag;
		v -> r -> tag = v -> tag;
	}
	v -> tag = 0;
}

void upd (Node *v, int l, int r, int val, int tl = 1, int tr = M) {
	push(v, tl, tr);
	if (tl > r || tr < l) return;
	if (tl >= l && tr <= r) {
	    v -> tag = val;
		push(v, tl, tr);
		return;
	}
	f(v -> l);
	f(v -> r);
	int tm = (tl + tr) >> 1;
	upd(v -> l, l, r, val, tl, tm);
	upd(v -> r, l, r, val, tm + 1, tr);
	v -> sum = (v -> l -> sum) + (v -> r -> sum);
}

int get (Node *v, int l, int r, int tl = 1, int tr = M) {
	push(v, tl, tr);
	if (tl > r || tr < l) return 0;
	if (tl >= l && tr <= r) return v -> sum;
	f(v -> l);
	f(v -> r);
	int tm = (tl + tr) >> 1;
	int a = get(v -> l, l, r, tl, tm);
	int b = get(v -> r, l, r, tm + 1, tr);
	return a + b;
}

void solve () {
	cin >> n;
	Node *root = new Node();
	int c = 0;
	for (int i = 1; i <= n; i++) {
		int tp, x, y;
		cin >> tp >> x >> y;
		if (tp == 1) {
			c = get(root, x + c, y + c);
			cout << c << '\n';
		}
		if (tp == 2) upd(root, x + c, y + c, 1);
	}
	cout << '\n';	
}                                              

bool testcases = 0;

signed main() {
#ifdef ONLINE_JUDGE
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
    cin.tie(0) -> sync_with_stdio(0);
    int test = 1;
    if (testcases) cin >> test;
    for (int cs = 1; cs <= test; cs++) {
        solve();
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	15 ms	8596 KB	Output is correct
5	Correct	19 ms	10316 KB	Output is correct
6	Correct	18 ms	9948 KB	Output is correct
7	Correct	19 ms	10264 KB	Output is correct
8	Correct	154 ms	77044 KB	Output is correct
9	Correct	315 ms	130832 KB	Output is correct
10	Correct	334 ms	146908 KB	Output is correct
11	Correct	331 ms	159312 KB	Output is correct
12	Correct	369 ms	164876 KB	Output is correct
13	Correct	339 ms	204936 KB	Output is correct
14	Correct	324 ms	206976 KB	Output is correct
15	Runtime error	366 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-