Submission #525589

#	Time	Username	Problem	Language	Result	Execution time	Memory
525589		shmad	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	428 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);
const double eps = 1e-6;

int n;

struct Node {
	int sum, tag;
	Node *l, *r;
	Node () : sum(0), tag(0), l(nullptr), r(nullptr) {}
	Node (Node *x, Node *y) : l(x), r(y), sum(0), tag(0) { sum += (x ? x -> sum : 0) + (y ? y -> sum : 0); }
}*root;                              

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

void push (Node* &v, int tl, int tr) {
	f(v -> l);
	f(v -> r);
	if (v -> tag) {
		v -> sum = (tr - tl + 1) * v -> tag;
		if (tl != tr) {
			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 = mod) {
	if (!v) return;
	push(v, tl, tr);
	if (tl > r || tr < l) return;
	if (tl >= l && tr <= r) {
	    v -> tag = val;
		push(v, tl, tr);
		return;
	}
	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 ? v -> l -> sum : 0) + (v -> r ? v -> r -> sum : 0);
}

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

void solve () {
	cin >> n;
	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();
    }
}

Compilation message (stderr)

apple.cpp: In constructor 'Node::Node(Node*, Node*)':
apple.cpp:27:12: warning: 'Node::r' will be initialized after [-Wreorder]
   27 |  Node *l, *r;
      |            ^
apple.cpp:26:6: warning:   'long long int Node::sum' [-Wreorder]
   26 |  int sum, tag;
      |      ^~~
apple.cpp:29:2: warning:   when initialized here [-Wreorder]
   29 |  Node (Node *x, Node *y) : l(x), r(y), sum(0), tag(0) { sum += (x ? x -> sum : 0) + (y ? y -> sum : 0); }
      |  ^~~~
apple.cpp: In function 'void upd(Node*, long long int, long long int, long long int, long long int, long long int)':
apple.cpp:58:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |  int tm = tl + tr >> 1;
      |           ~~~^~~~
apple.cpp: In function 'long long int get(Node*, long long int, long long int, long long int, long long int)':
apple.cpp:69:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |  int tm = tl + tr >> 1;
      |           ~~~^~~~

• Subtask 1: 0 / 100