oj.uz

Submission #556185

# Submission time Handle Problem Language Result Execution time Memory
556185 2022-05-02T14:53:53 Z Zanite Game (IOI13_game) C++17
100 / 100
 3541 ms 68764 KB 
#include "game.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long

long long gcd2(long long X, long long Y) {
    if (!X) return Y;
	if (!Y) return X;
	return gcd2(Y, X % Y);
}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Treap {
	struct Node {
		ll val, g;
		ll prior, pos, mn, mx;
		Node *left, *right;

		Node(ll _pos, ll _val) {
			pos = mn = mx = _pos;
			val = g = _val;
			prior = rng();
			left = right = nullptr;
		}
		
		void update() {
			g = val;
			if (left) {g = gcd2(g, left->g);}
			if (right) {g = gcd2(g, right->g);}

			mn = (left ? left->mn : pos);
			mx = (right ? right->mx : pos);
		}
	};

	Node *root;

	Treap() : root(nullptr) {}

	void split(Node *T, Node *&L, Node *&R, ll sep) {
		// splits T into L = [mn..pos] and R = [pos+1..mx]
		if (!T) {
			L = R = nullptr;
			return;
		}

		if (T->pos <= sep) {
			split(T->right, T->right, R, sep);
			L = T;
		} else {
			split(T->left, L, T->left, sep);
			R = T;
		}

		T->update();
	}

	void merge(Node *&T, Node *L, Node *R) {
		// merges L and R into T, assuming that all elements in L < R
		if (!L || !R) {
			T = (L ? L : R);
			return;
		}

		if (L->prior >= R->prior) {
			merge(L->right, L->right, R);
			T = L;
		} else {
			merge(R->left, L, R->left);
			T = R;
		}

		T->update();
	}

	bool find(ll pos) {
		// returns TRUE if the node with position pos is present in the treap
		Node *cur = root;
		while (cur) {
			if (cur->pos == pos) {return true;}
			if (cur->pos < pos) {cur = cur->right;}
			else {cur = cur->left;}
		}
		return false;
	}

	void updateNode(Node *cur, ll pos, ll val) {
		// updates node at position pos with val, assuming the node exists
		if (cur->pos == pos) {
			cur->val = val;
			cur->update();
			return;
		}
		
		if (cur->pos < pos) {
			updateNode(cur->right, pos, val);
		} else {
			updateNode(cur->left, pos, val);
		}
		cur->update();
	}

	void update(ll pos, ll val) {
		// if the node exists, update it
		if (find(pos)) {updateNode(root, pos, val);}
		else {
			// insert a new node
			Node *tmp = new Node(pos, val);
			Node *t1, *t2;
			split(root, t1, t2, pos);
			merge(root, t1, tmp);
			merge(root, root, t2);
		}
	}

	ll query(Node *T, ll L, ll R) {
		// returns sum of all nodes in the range [L..R] under node T
		if (!T) return 0;
		if (T->mx < L || R < T->mn) return 0;
		if (L <= T->mn && T->mx <= R) return T->g;

		ll ret = (L <= T->pos && T->pos <= R) ? (T->val) : 0;
		if (T->left) {ret = gcd2(ret, query(T->left, L, R));}
		if (T->right) {ret = gcd2(ret, query(T->right, L, R));}
		return ret;
	}

	ll query(ll L, ll R) {
		// returns sum of all nodes in the range [L..R]
		return query(root, L, R);
	}

	void print(Node *T) {
		if (!T) return;
		cout << T->pos << ' ' << T->val << ' ' << T->g << ' ' << T->mn << ' ' << T->mx << '\n';
		print(T->left);
		print(T->right);
	}

	void print() {
		print(root);
	}
};

struct DynamicSegtreeBBST {
	struct Node {
		Treap inner;
		Node* left;
		Node* right;

		Node() {
			inner = Treap();
			left = right = nullptr;
		}

		void update(ll pos) {
			ll tmp = 0;
			if (left) {tmp = gcd(tmp, left->inner.query(pos, pos));}
			if (right) {tmp = gcd(tmp, right->inner.query(pos, pos));}
			inner.update(pos, tmp);
		}
	};

	Node* root;
	ll dim1, dim2;

	DynamicSegtreeBBST(ll _dim1, ll _dim2) {
		root = new Node();
		dim1 = _dim1, dim2 = _dim2;
	}

	void update(Node* cur, ll l, ll r, ll d1, ll d2, ll upd) {
		if (l == r) {
			cur->inner.update(d2, upd);
			return;
		}

		ll m = (l + r) >> 1;
		if (d1 <= m) {
			if (!cur->left) {cur->left = new Node();}
			update(cur->left, l, m, d1, d2, upd);
		} else {
			if (!cur->right) {cur->right = new Node();}
			update(cur->right, m+1, r, d1, d2, upd);
		}
		cur->update(d2);
	}

	ll query(Node* cur, ll l, ll r, ll d1l, ll d1r, ll d2l, ll d2r) {
		if (l > d1r || d1l > r) {return 0;}
		if (d1l <= l && r <= d1r) {return cur->inner.query(d2l, d2r);}

		ll m = (l + r) >> 1, ret = 0;
		if (cur->left) {ret = gcd2(ret, query(cur->left, l, m, d1l, d1r, d2l, d2r));}
		if (cur->right) {ret = gcd2(ret, query(cur->right, m+1, r, d1l, d1r, d2l, d2r));}
		return ret;
	}

    void print() {
        for (ll i = 1; i <= dim1; i++) {
            for (ll j = 1; j <= dim2; j++) {
                cout << query(root, 1, dim1, i, i, j, j) << ' ';
            }
            cout << '\n';
        }
        cout << '\n';
    }
};

DynamicSegtreeBBST *D;
int R, C;

void init(int R, int C) {
    ::R = R;
    ::C = C;
    D = new DynamicSegtreeBBST(R, C);
}

void update(int P, int Q, long long K) {
    D->update(D->root, 1, R, P+1, Q+1, K);
}

long long calculate(int P, int Q, int U, int V) {
    return D->query(D->root, 1, R, P+1, U+1, Q+1, V+1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 557 ms 9192 KB Output is correct
5 Correct 282 ms 9420 KB Output is correct
6 Correct 535 ms 6452 KB Output is correct
7 Correct 637 ms 5916 KB Output is correct
8 Correct 377 ms 5124 KB Output is correct
9 Correct 610 ms 6016 KB Output is correct
10 Correct 585 ms 5684 KB Output is correct
11 Correct 1 ms 304 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 769 ms 11956 KB Output is correct
13 Correct 1203 ms 5916 KB Output is correct
14 Correct 221 ms 2420 KB Output is correct
15 Correct 1284 ms 6936 KB Output is correct
16 Correct 255 ms 10136 KB Output is correct
17 Correct 768 ms 7108 KB Output is correct
18 Correct 1567 ms 10816 KB Output is correct
19 Correct 1272 ms 10664 KB Output is correct
20 Correct 1187 ms 9960 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 547 ms 9124 KB Output is correct
13 Correct 266 ms 9652 KB Output is correct
14 Correct 568 ms 6196 KB Output is correct
15 Correct 660 ms 6068 KB Output is correct
16 Correct 411 ms 5020 KB Output is correct
17 Correct 602 ms 6104 KB Output is correct
18 Correct 574 ms 5640 KB Output is correct
19 Correct 758 ms 11872 KB Output is correct
20 Correct 1149 ms 5836 KB Output is correct
21 Correct 229 ms 2440 KB Output is correct
22 Correct 1179 ms 6860 KB Output is correct
23 Correct 313 ms 10204 KB Output is correct
24 Correct 789 ms 7128 KB Output is correct
25 Correct 1465 ms 10604 KB Output is correct
26 Correct 1178 ms 10612 KB Output is correct
27 Correct 1188 ms 9984 KB Output is correct
28 Correct 468 ms 32044 KB Output is correct
29 Correct 1285 ms 35260 KB Output is correct
30 Correct 1534 ms 27148 KB Output is correct
31 Correct 1354 ms 21236 KB Output is correct
32 Correct 295 ms 2420 KB Output is correct
33 Correct 417 ms 3080 KB Output is correct
34 Correct 368 ms 32224 KB Output is correct
35 Correct 946 ms 17996 KB Output is correct
36 Correct 2071 ms 32576 KB Output is correct
37 Correct 1650 ms 32844 KB Output is correct
38 Correct 1586 ms 32244 KB Output is correct
39 Correct 1288 ms 25696 KB Output is correct
40 Correct 1 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 530 ms 9108 KB Output is correct
13 Correct 247 ms 9420 KB Output is correct
14 Correct 550 ms 6224 KB Output is correct
15 Correct 643 ms 6072 KB Output is correct
16 Correct 365 ms 5108 KB Output is correct
17 Correct 610 ms 6100 KB Output is correct
18 Correct 576 ms 5588 KB Output is correct
19 Correct 803 ms 11728 KB Output is correct
20 Correct 1178 ms 5708 KB Output is correct
21 Correct 214 ms 2332 KB Output is correct
22 Correct 1267 ms 6760 KB Output is correct
23 Correct 267 ms 9848 KB Output is correct
24 Correct 753 ms 6884 KB Output is correct
25 Correct 1488 ms 10224 KB Output is correct
26 Correct 1273 ms 10448 KB Output is correct
27 Correct 1338 ms 10076 KB Output is correct
28 Correct 471 ms 32116 KB Output is correct
29 Correct 1554 ms 35052 KB Output is correct
30 Correct 1616 ms 27052 KB Output is correct
31 Correct 1486 ms 21320 KB Output is correct
32 Correct 300 ms 2464 KB Output is correct
33 Correct 512 ms 3128 KB Output is correct
34 Correct 437 ms 32080 KB Output is correct
35 Correct 1020 ms 17636 KB Output is correct
36 Correct 2160 ms 32292 KB Output is correct
37 Correct 1617 ms 32520 KB Output is correct
38 Correct 1665 ms 32016 KB Output is correct
39 Correct 611 ms 66592 KB Output is correct
40 Correct 2296 ms 68764 KB Output is correct
41 Correct 2288 ms 55332 KB Output is correct
42 Correct 2068 ms 41912 KB Output is correct
43 Correct 819 ms 66828 KB Output is correct
44 Correct 405 ms 2188 KB Output is correct
45 Correct 1498 ms 25368 KB Output is correct
46 Correct 3541 ms 66980 KB Output is correct
47 Correct 3197 ms 66992 KB Output is correct
48 Correct 3149 ms 66668 KB Output is correct
49 Correct 1 ms 212 KB Output is correct