Submission #525453

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
525453	2022-02-11T16:38:15 Z	shmad	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	400 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);
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 *l, Node *r) : l(l), r(r), sum(0), tag(0) { sum += (l ? l -> sum : 0) + (r ? r -> 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) {
	push(v, tl, tr);
	if (tl > r || tr < l || !v) 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 = mod) {
	push(v, tl, tr);
	if (tl > r || tr < l || !v) 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;
	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

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 *l, Node *r) : l(l), r(r), sum(0), tag(0) { sum += (l ? l -> sum : 0) + (r ? r -> 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:59:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |  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:71:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |  int tm = tl + tr >> 1;
      |           ~~~^~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	308 KB	Output is correct
3	Correct	1 ms	312 KB	Output is correct
4	Correct	18 ms	9404 KB	Output is correct
5	Correct	29 ms	11488 KB	Output is correct
6	Correct	23 ms	11168 KB	Output is correct
7	Correct	22 ms	11488 KB	Output is correct
8	Correct	176 ms	87780 KB	Output is correct
9	Correct	355 ms	152120 KB	Output is correct
10	Correct	365 ms	168300 KB	Output is correct
11	Correct	400 ms	180808 KB	Output is correct
12	Correct	385 ms	186388 KB	Output is correct
13	Correct	379 ms	217360 KB	Output is correct
14	Correct	359 ms	219320 KB	Output is correct
15	Runtime error	376 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-