Submission #525600

#	Time	Username	Problem	Language	Result	Execution time	Memory
525600		shmad	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	369 ms	262148 KiB

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