oj.uz

Submission #556180

# Submission time Handle Problem Language Result Execution time Memory
556180 2022-05-02T14:48:01 Z Zanite Game (IOI13_game) C++17
100 / 100
 2871 ms 78404 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) {
			//cout << "{" << T->mn << ", " << T->mx << ": " << T->g << "} ";
			return T->g;
		}

		ll ret;
		if (L <= T->pos && T->pos <= R) {
			//cout << "{" << T->pos << ", " << T->pos << ": " << T->val << "} ";
			ret = T->val;
		} else {
			ret = 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) {
			//debug(l); debug(r);
			//cur->inner.print();
			//cout << "{" << l << ", " << r << "} : ";
			ll ret = cur->inner.query(d2l, d2r);
			//cout << ": " << ret << '\n';
			//debug(ret);
			return ret;
		}

		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);
    //D->print();
}

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 304 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 304 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 304 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 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 583 ms 12136 KB Output is correct
5 Correct 302 ms 11868 KB Output is correct
6 Correct 560 ms 9392 KB Output is correct
7 Correct 632 ms 9124 KB Output is correct
8 Correct 405 ms 7892 KB Output is correct
9 Correct 555 ms 9156 KB Output is correct
10 Correct 558 ms 8736 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 9 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 300 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 308 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 766 ms 14532 KB Output is correct
13 Correct 1168 ms 8312 KB Output is correct
14 Correct 230 ms 5624 KB Output is correct
15 Correct 1240 ms 9932 KB Output is correct
16 Correct 291 ms 12808 KB Output is correct
17 Correct 761 ms 10508 KB Output is correct
18 Correct 1457 ms 14364 KB Output is correct
19 Correct 1158 ms 14460 KB Output is correct
20 Correct 1164 ms 13992 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 300 KB Output is correct
2 Correct 1 ms 300 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 260 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 304 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 526 ms 12084 KB Output is correct
13 Correct 275 ms 11820 KB Output is correct
14 Correct 519 ms 9376 KB Output is correct
15 Correct 585 ms 9092 KB Output is correct
16 Correct 364 ms 7692 KB Output is correct
17 Correct 676 ms 9268 KB Output is correct
18 Correct 527 ms 8756 KB Output is correct
19 Correct 727 ms 14548 KB Output is correct
20 Correct 1140 ms 8508 KB Output is correct
21 Correct 241 ms 5500 KB Output is correct
22 Correct 1180 ms 9872 KB Output is correct
23 Correct 254 ms 12736 KB Output is correct
24 Correct 734 ms 10468 KB Output is correct
25 Correct 1450 ms 14180 KB Output is correct
26 Correct 1198 ms 14504 KB Output is correct
27 Correct 1129 ms 13900 KB Output is correct
28 Correct 458 ms 41164 KB Output is correct
29 Correct 1168 ms 43840 KB Output is correct
30 Correct 1479 ms 32660 KB Output is correct
31 Correct 1383 ms 26624 KB Output is correct
32 Correct 299 ms 10188 KB Output is correct
33 Correct 425 ms 10544 KB Output is correct
34 Correct 384 ms 37468 KB Output is correct
35 Correct 966 ms 26264 KB Output is correct
36 Correct 2194 ms 41548 KB Output is correct
37 Correct 1711 ms 41912 KB Output is correct
38 Correct 1683 ms 41316 KB Output is correct
39 Correct 1274 ms 34492 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 304 KB Output is correct
2 Correct 2 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 340 KB Output is correct
12 Correct 540 ms 12108 KB Output is correct
13 Correct 254 ms 11996 KB Output is correct
14 Correct 514 ms 9324 KB Output is correct
15 Correct 582 ms 9048 KB Output is correct
16 Correct 364 ms 7728 KB Output is correct
17 Correct 561 ms 9152 KB Output is correct
18 Correct 529 ms 8820 KB Output is correct
19 Correct 701 ms 14540 KB Output is correct
20 Correct 1089 ms 8396 KB Output is correct
21 Correct 213 ms 5616 KB Output is correct
22 Correct 1175 ms 10008 KB Output is correct
23 Correct 258 ms 12828 KB Output is correct
24 Correct 697 ms 10412 KB Output is correct
25 Correct 1362 ms 14340 KB Output is correct
26 Correct 1115 ms 14368 KB Output is correct
27 Correct 1016 ms 13852 KB Output is correct
28 Correct 487 ms 41108 KB Output is correct
29 Correct 1171 ms 43724 KB Output is correct
30 Correct 1420 ms 32604 KB Output is correct
31 Correct 1273 ms 26624 KB Output is correct
32 Correct 283 ms 10188 KB Output is correct
33 Correct 399 ms 10576 KB Output is correct
34 Correct 354 ms 37512 KB Output is correct
35 Correct 926 ms 26272 KB Output is correct
36 Correct 1974 ms 41868 KB Output is correct
37 Correct 1530 ms 42148 KB Output is correct
38 Correct 1588 ms 41408 KB Output is correct
39 Correct 614 ms 76096 KB Output is correct
40 Correct 2179 ms 78404 KB Output is correct
41 Correct 2329 ms 61492 KB Output is correct
42 Correct 2083 ms 48524 KB Output is correct
43 Correct 749 ms 73164 KB Output is correct
44 Correct 393 ms 10784 KB Output is correct
45 Correct 1222 ms 34756 KB Output is correct
46 Correct 2866 ms 77284 KB Output is correct
47 Correct 2871 ms 77116 KB Output is correct
48 Correct 2833 ms 76868 KB Output is correct
49 Correct 1 ms 212 KB Output is correct