oj.uz

Submission #140300

# Submission time Handle Problem Language Result Execution time Memory
140300 2019-08-02T13:46:59 Z Noam527 Game (IOI13_game) C++17
100 / 100
 6036 ms 73516 KB 
#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 9e18;
using namespace std;

#include "game.h"
// moving code from wcipeg is pain

ll gcd(ll x, ll y) {
	return !y ? x : gcd(y, x % y);
}
int rnd() {
	return ((rand() % (1 << 15)) << 16) + (rand() % (1 << 15));
}

struct node {
	node *l, *r;
	int pos, key, mn, mx;
	ll val, g;
	node(int position, ll value) {
		l = r = nullptr;
		mn = mx = pos = position;
		key = rnd();
		val = g = value;
	}
	void upd() {
		g = val;
		if (l) g = gcd(g, l->g);
		if (r) g = gcd(g, r->g);
		mn = (l ? l->mn : pos);
		mx = (r ? r->mx : pos);
	}
};
struct treap {
	node *root;
	treap() {
		root = nullptr;
		srand(rnd());
	}
	void split(node *t, int pos, node *&l, node *&r) {
		if (t == nullptr) {
			l = r = nullptr;
			return;
		}
		if (t->pos < pos) {
			split(t->r, pos, l, r);
			t->r = l;
			l = t;
		}
		else {
			split(t->l, pos, l, r);
			t->l = r;
			r = t;
		}
		t->upd();
	}
	node* merge(node *l, node *r) {
		if (!l || !r) return l ? l : r;
		if (l->key < r->key) {
			l->r = merge(l->r, r);
			l->upd();
			return l;
		}
		r->l = merge(l, r->l);
		r->upd();
		return r;
	}
	bool find(int pos) {
		node *t = root;
		while (t) {
			if (t->pos == pos) return true;
			if (t->pos > pos) t = t->l;
			else t = t->r;
		}
		return false;
	}
	void upd(node *t, int pos, ll val) {
		if (t->pos == pos) {
			t->val = val;
			t->upd();
			return;
		}
		if (t->pos > pos)
			upd(t->l, pos, val);
		else
			upd(t->r, pos, val);
		t->upd();
	}
	void insert(int pos, ll val) {
		if (find(pos)) upd(root, pos, val);
		else {
			node *l, *r;
			split(root, pos, l, r);
			root = merge(merge(l, new node(pos, val)), r);
		}
	}
	ll query(node *t, int st, int en) {
		if (t->mx < st || en < t->mn) return 0;
		if (st <= t->mn && t->mx <= en) return t->g;
		ll rtn = (st <= t->pos && t->pos <= en ? t->val : 0);
		if (t->l) rtn = gcd(rtn, query(t->l, st, en));
		if (t->r) rtn = gcd(rtn, query(t->r, st, en));
		return rtn;
	}
	ll query(int st, int en) {
		if (!root) return 0;
		return query(root, st, en);
	}
	void print(node *t) {
		if (!t) return;
		print(t->l);
		cout << t->val << " ";
		print(t->r);
	}
};
struct segtree {
	segtree *l, *r;
	treap T;
	int lo, hi;
	segtree() {
		l = r = nullptr;
	}
	segtree(int st, int en) {
		l = r = nullptr;
		lo = st, hi = en;
	}
	void createl() {
		if (!l) l = new segtree(lo, (lo + hi) / 2);
	}
	void creater() {
		if (!r) r = new segtree((lo + hi) / 2 + 1, hi);
	}
	void fix(int pos) {
		ll val = 0;
		if (l) val = gcd(val, l->T.query(pos, pos));
		if (r) val = gcd(val, r->T.query(pos, pos));
		T.insert(pos, val);
	}
	void upd(int x, int y, ll val) {
		if (hi < x || x < lo) return;
		if (lo == hi) {
			T.insert(y, val);
			return;
		}
		if (lo != hi) {
			if (x <= (lo + hi) / 2) {
				createl();
				l->upd(x, y, val);
			}
			else {
				creater();
				r->upd(x, y, val);
			}
		}
		fix(y);
	}
	ll query(int t, int b, int st, int en) {
		if (hi < t || b < lo) return 0;
		if (t <= lo && hi <= b) return T.query(st, en);
		ll rtn = 0;
		if (l)
			rtn = gcd(rtn, l->query(t, b, st, en));
		if (r)
			rtn = gcd(rtn, r->query(t, b, st, en));
		return rtn;
	}
};

int r, c, q;
segtree T;

void init(int R, int C) {
	srand(12341234);
	r = R;
	c = C;
	T = segtree(0, r - 1);
}
void update(int P, int Q, ll K) {
	T.upd(P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
	return T.query(P, U, Q, V);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 252 KB Output is correct
9 Correct 3 ms 380 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 296 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 1197 ms 10200 KB Output is correct
5 Correct 498 ms 10204 KB Output is correct
6 Correct 1051 ms 7924 KB Output is correct
7 Correct 1174 ms 7676 KB Output is correct
8 Correct 662 ms 6424 KB Output is correct
9 Correct 1147 ms 7800 KB Output is correct
10 Correct 1213 ms 7312 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 1642 ms 11832 KB Output is correct
13 Correct 2589 ms 6896 KB Output is correct
14 Correct 332 ms 4188 KB Output is correct
15 Correct 2817 ms 8312 KB Output is correct
16 Correct 451 ms 10104 KB Output is correct
17 Correct 1450 ms 9464 KB Output is correct
18 Correct 2671 ms 12488 KB Output is correct
19 Correct 2235 ms 12424 KB Output is correct
20 Correct 2400 ms 11816 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 1120 ms 11268 KB Output is correct
13 Correct 445 ms 11260 KB Output is correct
14 Correct 1050 ms 8184 KB Output is correct
15 Correct 1175 ms 8416 KB Output is correct
16 Correct 671 ms 7292 KB Output is correct
17 Correct 1122 ms 8440 KB Output is correct
18 Correct 1126 ms 8188 KB Output is correct
19 Correct 1602 ms 12904 KB Output is correct
20 Correct 2591 ms 6648 KB Output is correct
21 Correct 333 ms 5052 KB Output is correct
22 Correct 2811 ms 8660 KB Output is correct
23 Correct 449 ms 10748 KB Output is correct
24 Correct 1457 ms 9312 KB Output is correct
25 Correct 2650 ms 12596 KB Output is correct
26 Correct 2284 ms 12768 KB Output is correct
27 Correct 2320 ms 12200 KB Output is correct
28 Correct 1000 ms 30584 KB Output is correct
29 Correct 2658 ms 41908 KB Output is correct
30 Correct 3319 ms 30096 KB Output is correct
31 Correct 2916 ms 24796 KB Output is correct
32 Correct 529 ms 10248 KB Output is correct
33 Correct 773 ms 10716 KB Output is correct
34 Correct 904 ms 35664 KB Output is correct
35 Correct 1912 ms 25336 KB Output is correct
36 Correct 3750 ms 39832 KB Output is correct
37 Correct 3172 ms 39912 KB Output is correct
38 Correct 3356 ms 39276 KB Output is correct
39 Correct 2645 ms 33044 KB Output is correct
40 Correct 2 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 3 ms 400 KB Output is correct
3 Correct 3 ms 356 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 3 ms 396 KB Output is correct
12 Correct 1120 ms 11416 KB Output is correct
13 Correct 449 ms 11404 KB Output is correct
14 Correct 1039 ms 8828 KB Output is correct
15 Correct 1189 ms 8564 KB Output is correct
16 Correct 668 ms 7532 KB Output is correct
17 Correct 1143 ms 8700 KB Output is correct
18 Correct 1127 ms 8184 KB Output is correct
19 Correct 1631 ms 13452 KB Output is correct
20 Correct 2606 ms 7800 KB Output is correct
21 Correct 336 ms 5628 KB Output is correct
22 Correct 2831 ms 7856 KB Output is correct
23 Correct 458 ms 11380 KB Output is correct
24 Correct 1457 ms 9916 KB Output is correct
25 Correct 3008 ms 12976 KB Output is correct
26 Correct 2429 ms 13220 KB Output is correct
27 Correct 2273 ms 12492 KB Output is correct
28 Correct 1014 ms 31396 KB Output is correct
29 Correct 2896 ms 41852 KB Output is correct
30 Correct 3289 ms 30072 KB Output is correct
31 Correct 2926 ms 24868 KB Output is correct
32 Correct 531 ms 10232 KB Output is correct
33 Correct 775 ms 10616 KB Output is correct
34 Correct 908 ms 35480 KB Output is correct
35 Correct 1940 ms 25504 KB Output is correct
36 Correct 3976 ms 39716 KB Output is correct
37 Correct 3281 ms 40124 KB Output is correct
38 Correct 3431 ms 39400 KB Output is correct
39 Correct 1637 ms 71352 KB Output is correct
40 Correct 4717 ms 73516 KB Output is correct
41 Correct 5309 ms 55360 KB Output is correct
42 Correct 4786 ms 43964 KB Output is correct
43 Correct 2071 ms 68036 KB Output is correct
44 Correct 766 ms 10744 KB Output is correct
45 Correct 2693 ms 33248 KB Output is correct
46 Correct 5809 ms 72328 KB Output is correct
47 Correct 5832 ms 72196 KB Output is correct
48 Correct 6036 ms 71864 KB Output is correct
49 Correct 2 ms 256 KB Output is correct