oj.uz

Submission #151677

# Submission time Handle Problem Language Result Execution time Memory
151677 2019-09-04T06:01:02 Z qkxwsm Game (IOI13_game) C++14
80 / 100
 13000 ms 67572 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define y1 qwertyuiop
#define y2 asdfghjkl
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define INF 1000000007
#define LLINF 2696969696969696969

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, M;

ll gcd(ll a, ll b)
{
	return (b == 0 ? a : gcd(b, a % b));
}

struct node
{
	pii idx;
	int pri;
	ll cur, stor;
	node *ch[2];
	node(pii x, ll v)
	{
		idx = x; pri = (rand() << 15 + rand()) % INF;
		cur = v; stor = v;
		ch[0] = nullptr; ch[1] = nullptr;
	}
};

void pull(node *t)
{
	if (!t) return;
	t -> stor = t -> cur;
	if (t -> ch[0]) t -> stor = gcd(t -> stor, t -> ch[0] -> stor);
	if (t -> ch[1]) t -> stor = gcd(t -> stor, t -> ch[1] -> stor);
	return;
}
typedef pair<node*, node*> pnn;
node *merge(node *l, node *r)
{
	if (!l) return r;
	if (!r) return l;
	if (l -> pri > r -> pri)
	{
		l -> ch[1] = merge(l -> ch[1], r);
		pull(l); return l;
	}
	else
	{
		r -> ch[0] = merge(l, r -> ch[0]);
		pull(r); return r;
	}
}
pnn split(node *t, pii v)
{
	if (!t) return {t, t};
	pii cur = t -> idx;
	if (v > cur)
	{
		pnn p = split(t -> ch[1], v);
		t -> ch[1] = p.fi; pull(t);
		return {t, p.se};
	}
	else
	{
		pnn p = split(t -> ch[0], v);
		t -> ch[0] = p.se; pull(t);
		return {p.fi, t};
	}
}

void inorder(node *t)
{
	if (!t) return;
	inorder(t -> ch[0]);
	cerr << t -> idx.fi << ',' << t -> cur << ' ';
	inorder(t -> ch[1]);
}

struct Node
{
	node *root;
	Node *ch[2];
	Node()
	{
		root = nullptr;
		ch[0] = nullptr;
		ch[1] = nullptr;
	}
};

Node *root;

Node* upd(Node *t, int L, int R, int a, int y, ll v)
{
	if (!t) t = new Node();
	pnn p = split(t -> root, {y, a}), p1 = split(p.se, {y, a + 1});
	t -> root = merge(p.fi, merge(new node({y, a}, v), p1.se));
	// cerr << "PUSH\n";
	// cerr << L << " -> " << R << endl;
	// inorder(t -> root);
	// cerr << endl;
	if (L != R)
	{
		int mid = (L + R) >> 1;
		if (a <= mid)
		{
			t -> ch[0] = upd(t -> ch[0], L, mid, a, y, v);
		}
		else
		{
			t -> ch[1] = upd(t -> ch[1], mid + 1, R, a, y, v);
		}
	}
	return t;
}
ll qry(Node *t, int L, int R, int a, int b, int y1, int y2)
{
	// cerr << (t ? "YES" : "NO") << endl;
	// cerr << "WORK " << y1 << ' ' << y2 << endl;
	if (!t) return 0;
	if (a <= L && R <= b)
	{
		// cerr << "PULL\n";
		// cerr << L << " -> " << R << endl;
		// inorder(t -> root);
		// cerr << endl;
		pnn p = split(t -> root, {y1, 0}), p1 = split(p.se, {y2 + 1, 0});
		// cerr << "SOLVE\n";
		// cerr << L << " -> " << R << endl;
		// inorder(p1.fi);
		// cerr << endl;
		ll res = (p1.fi ? p1.fi -> stor : 0);
		t -> root = merge(p.fi, merge(p1.fi, p1.se));
		return res;
	}
	int mid = (L + R) >> 1;
	if (b <= mid) return qry(t -> ch[0], L, mid, a, b, y1, y2);
	if (mid < a) return qry(t -> ch[1], mid + 1, R, a, b, y1, y2);
	return gcd(qry(t -> ch[0], L, mid, a, b, y1, y2), qry(t -> ch[1], mid + 1, R, a, b, y1, y2));
}

void init(int n, int m)
{
	N = n; M = m;
	srand(69);
}

void update(int x, int y, ll v)
{
	root = upd(root, 0, N - 1, x, y, v);
}

ll calculate(int x1, int y1, int x2, int y2)
{
	// cerr << x1 << ' ' << x2 << ' ' << y1 << ' ' << y2 << endl;
	return qry(root, 0, N - 1, x1, x2, y1, y2);
}

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;
      ^~~
game.cpp: In constructor 'node::node(pii, ll)':
game.cpp:56:32: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   idx = x; pri = (rand() << 15 + rand()) % INF;
                             ~~~^~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 256 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 256 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 364 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 2 ms 380 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 252 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 1911 ms 11616 KB Output is correct
5 Correct 740 ms 11308 KB Output is correct
6 Correct 2581 ms 8908 KB Output is correct
7 Correct 2946 ms 8520 KB Output is correct
8 Correct 1952 ms 7500 KB Output is correct
9 Correct 2854 ms 8756 KB Output is correct
10 Correct 2679 ms 8496 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 504 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 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3191 ms 15468 KB Output is correct
13 Correct 8412 ms 12068 KB Output is correct
14 Correct 1317 ms 13360 KB Output is correct
15 Correct 9219 ms 13104 KB Output is correct
16 Correct 1038 ms 13064 KB Output is correct
17 Correct 4287 ms 10316 KB Output is correct
18 Correct 7848 ms 14572 KB Output is correct
19 Correct 6541 ms 14708 KB Output is correct
20 Correct 7294 ms 13928 KB Output is correct
21 Correct 2 ms 256 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 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 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 3 ms 380 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 1917 ms 11592 KB Output is correct
13 Correct 720 ms 11384 KB Output is correct
14 Correct 2539 ms 8752 KB Output is correct
15 Correct 3082 ms 8676 KB Output is correct
16 Correct 1975 ms 7536 KB Output is correct
17 Correct 2873 ms 8572 KB Output is correct
18 Correct 2744 ms 8392 KB Output is correct
19 Correct 3175 ms 15400 KB Output is correct
20 Correct 8359 ms 12024 KB Output is correct
21 Correct 1317 ms 13076 KB Output is correct
22 Correct 9122 ms 13368 KB Output is correct
23 Correct 1048 ms 12952 KB Output is correct
24 Correct 4319 ms 10292 KB Output is correct
25 Correct 7828 ms 14560 KB Output is correct
26 Correct 6548 ms 14744 KB Output is correct
27 Correct 7269 ms 13916 KB Output is correct
28 Correct 2053 ms 36336 KB Output is correct
29 Correct 4171 ms 39164 KB Output is correct
30 Correct 11218 ms 30480 KB Output is correct
31 Correct 9733 ms 29768 KB Output is correct
32 Correct 1733 ms 29516 KB Output is correct
33 Correct 2598 ms 29424 KB Output is correct
34 Correct 1121 ms 32700 KB Output is correct
35 Correct 4774 ms 23928 KB Output is correct
36 Correct 8999 ms 37028 KB Output is correct
37 Correct 7272 ms 37136 KB Output is correct
38 Correct 8159 ms 36624 KB Output is correct
39 Correct 6131 ms 31072 KB Output is correct
40 Correct 2 ms 256 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 1911 ms 11508 KB Output is correct
13 Correct 730 ms 11288 KB Output is correct
14 Correct 2537 ms 8968 KB Output is correct
15 Correct 2966 ms 8892 KB Output is correct
16 Correct 1934 ms 7532 KB Output is correct
17 Correct 2810 ms 8856 KB Output is correct
18 Correct 2666 ms 8172 KB Output is correct
19 Correct 3189 ms 15412 KB Output is correct
20 Correct 8266 ms 12100 KB Output is correct
21 Correct 1319 ms 13088 KB Output is correct
22 Correct 9185 ms 13172 KB Output is correct
23 Correct 1059 ms 13092 KB Output is correct
24 Correct 4328 ms 10212 KB Output is correct
25 Correct 7913 ms 14460 KB Output is correct
26 Correct 6487 ms 14512 KB Output is correct
27 Correct 7390 ms 14004 KB Output is correct
28 Correct 2085 ms 36420 KB Output is correct
29 Correct 3995 ms 39204 KB Output is correct
30 Correct 11116 ms 30352 KB Output is correct
31 Correct 9669 ms 29784 KB Output is correct
32 Correct 1706 ms 29580 KB Output is correct
33 Correct 2655 ms 29424 KB Output is correct
34 Correct 1130 ms 32736 KB Output is correct
35 Correct 4636 ms 23940 KB Output is correct
36 Correct 8782 ms 37036 KB Output is correct
37 Correct 7138 ms 37168 KB Output is correct
38 Correct 8114 ms 36512 KB Output is correct
39 Correct 2740 ms 65568 KB Output is correct
40 Correct 6751 ms 67572 KB Output is correct
41 Execution timed out 13083 ms 54140 KB Time limit exceeded
42 Halted 0 ms 0 KB -