oj.uz

답안 #957458

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
957458 2024-04-03T18:30:03 Z vjudge1 게임 (IOI13_game) C++17
100 / 100
 2851 ms 73484 KB 
// this shouldnt pass for the same reason my segtree solution doesnt pass, no?
#include "game.h"

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

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

struct TreapNode {
	TreapNode *l, *r;
	int pos, key, mn, mx;
	ll val, g;

	TreapNode(int position, ll value) {
		l = r = nullptr;
		mn = mx = pos = position;
		key = rnd();
		val = g = value;
	}

	void update() {
		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 {
	TreapNode *root;

	Treap() {
		root = nullptr;
		srand(rnd());
	}

	void split(TreapNode *t, int pos, TreapNode *&l, TreapNode *&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->update();
	}

	TreapNode *merge(TreapNode *l, TreapNode *r) {
		if (!l || !r) return l ? l : r;
		if (l->key < r->key) {
			l->r = merge(l->r, r);
			l->update();
			return l;
		} else {
			r->l = merge(l, r->l);
			r->update();
			return r;
		}
	}

	bool find(int pos) {
		TreapNode *t = root;
		while (t) {
			if (t->pos == pos) return true;
			if (t->pos > pos) t = t->l;
			else t = t->r;
		}
		return false;
	}

	void update(TreapNode *t, int pos, ll val) {
		if (t->pos == pos) {
			t->val = val;
			t->update();
			return;
		}
		if (t->pos > pos) update(t->l, pos, val);
		else update(t->r, pos, val);
		t->update();
	}

	void insert(int pos, ll val) {
		if (find(pos)) update(root, pos, val);
		else {
			TreapNode *l, *r;
			split(root, pos, l, r);
			root = merge(merge(l, new TreapNode(pos, val)), r);
		}
	}

	ll query(TreapNode *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 ans = (st <= t->pos && t->pos <= en ? t->val : 0);
		if (t->l) ans = gcd(ans, query(t->l, st, en));
		if (t->r) ans = gcd(ans, query(t->r, st, en));
		return ans;
	}
	ll query(int st, int en) {
		if (!root) return 0;
		return query(root, st, en);
	}
};

struct Segtree {
	Segtree *l, *r;
	Treap treap;
	int lo, hi;

	Segtree() { l = r = nullptr; }
	Segtree(int st, int en) {
		l = r = nullptr;
		lo = st, hi = en;
	}

	void new_left() {
		if (!l) l = new Segtree(lo, (lo + hi) / 2);
	}
	void new_right() {
		if (!r) r = new Segtree((lo + hi) / 2 + 1, hi);
	}
	void fix(int pos) {
		ll val = 0;
		if (l) val = gcd(val, l->treap.query(pos, pos));
		if (r) val = gcd(val, r->treap.query(pos, pos));
		treap.insert(pos, val);
	}

	void update(int x, int y, ll val) {
		if (hi < x || x < lo) return;
		if (lo == hi) {
			treap.insert(y, val);
			return;
		}

		if (x <= (lo + hi) / 2) {
			new_left();
			l->update(x, y, val);
		} else {
			new_right();
			r->update(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 treap.query(st, en);

		ll ans = 0;
		if (l) ans = gcd(ans, l->query(t, b, st, en));
		if (r) ans = gcd(ans, r->query(t, b, st, en));
		return ans;
	}
};

Segtree segtree;

void init(int R, int C) {
	srand(12341234);
	segtree = Segtree(0, R - 1);
}

void update(int P, int Q, ll K) { segtree.update(P, Q, K); }

ll calculate(int P, int Q, int U, int V) { return segtree.query(P, U, Q, V); }

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 386 ms 11568 KB Output is correct
5 Correct 185 ms 11344 KB Output is correct
6 Correct 404 ms 8804 KB Output is correct
7 Correct 452 ms 8532 KB Output is correct
8 Correct 286 ms 7616 KB Output is correct
9 Correct 429 ms 8532 KB Output is correct
10 Correct 420 ms 8372 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 519 ms 13244 KB Output is correct
13 Correct 832 ms 8024 KB Output is correct
14 Correct 161 ms 5616 KB Output is correct
15 Correct 903 ms 9212 KB Output is correct
16 Correct 196 ms 11344 KB Output is correct
17 Correct 575 ms 9688 KB Output is correct
18 Correct 923 ms 12932 KB Output is correct
19 Correct 864 ms 13152 KB Output is correct
20 Correct 809 ms 12376 KB Output is correct
21 Correct 0 ms 436 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 375 ms 11492 KB Output is correct
13 Correct 194 ms 11344 KB Output is correct
14 Correct 424 ms 8692 KB Output is correct
15 Correct 472 ms 8312 KB Output is correct
16 Correct 285 ms 7748 KB Output is correct
17 Correct 432 ms 8524 KB Output is correct
18 Correct 443 ms 8272 KB Output is correct
19 Correct 539 ms 13612 KB Output is correct
20 Correct 825 ms 7680 KB Output is correct
21 Correct 163 ms 5512 KB Output is correct
22 Correct 885 ms 8948 KB Output is correct
23 Correct 209 ms 11496 KB Output is correct
24 Correct 574 ms 9808 KB Output is correct
25 Correct 943 ms 12876 KB Output is correct
26 Correct 819 ms 12884 KB Output is correct
27 Correct 792 ms 12340 KB Output is correct
28 Correct 603 ms 39032 KB Output is correct
29 Correct 1118 ms 41700 KB Output is correct
30 Correct 1221 ms 29892 KB Output is correct
31 Correct 1074 ms 24860 KB Output is correct
32 Correct 228 ms 10324 KB Output is correct
33 Correct 308 ms 10576 KB Output is correct
34 Correct 562 ms 35692 KB Output is correct
35 Correct 832 ms 25424 KB Output is correct
36 Correct 1649 ms 39692 KB Output is correct
37 Correct 1377 ms 39816 KB Output is correct
38 Correct 1415 ms 39392 KB Output is correct
39 Correct 1105 ms 32992 KB Output is correct
40 Correct 1 ms 344 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 418 ms 11552 KB Output is correct
13 Correct 187 ms 11280 KB Output is correct
14 Correct 438 ms 8700 KB Output is correct
15 Correct 463 ms 8532 KB Output is correct
16 Correct 278 ms 7388 KB Output is correct
17 Correct 450 ms 8560 KB Output is correct
18 Correct 414 ms 8176 KB Output is correct
19 Correct 537 ms 13440 KB Output is correct
20 Correct 852 ms 7764 KB Output is correct
21 Correct 163 ms 5716 KB Output is correct
22 Correct 896 ms 9124 KB Output is correct
23 Correct 213 ms 11344 KB Output is correct
24 Correct 597 ms 10064 KB Output is correct
25 Correct 943 ms 12884 KB Output is correct
26 Correct 871 ms 13136 KB Output is correct
27 Correct 812 ms 12688 KB Output is correct
28 Correct 626 ms 38984 KB Output is correct
29 Correct 1162 ms 41696 KB Output is correct
30 Correct 1199 ms 29716 KB Output is correct
31 Correct 1091 ms 24832 KB Output is correct
32 Correct 229 ms 10316 KB Output is correct
33 Correct 311 ms 10764 KB Output is correct
34 Correct 612 ms 35412 KB Output is correct
35 Correct 892 ms 25268 KB Output is correct
36 Correct 1785 ms 39732 KB Output is correct
37 Correct 1438 ms 39868 KB Output is correct
38 Correct 1482 ms 39344 KB Output is correct
39 Correct 1075 ms 71376 KB Output is correct
40 Correct 2323 ms 73484 KB Output is correct
41 Correct 2043 ms 55564 KB Output is correct
42 Correct 1741 ms 43548 KB Output is correct
43 Correct 1207 ms 68312 KB Output is correct
44 Correct 310 ms 10712 KB Output is correct
45 Correct 1227 ms 33056 KB Output is correct
46 Correct 2746 ms 72200 KB Output is correct
47 Correct 2798 ms 72232 KB Output is correct
48 Correct 2851 ms 71812 KB Output is correct
49 Correct 0 ms 344 KB Output is correct