oj.uz

Submission #104909

# Submission time Handle Problem Language Result Execution time Memory
104909 2019-04-09T15:28:58 Z eriksuenderhauf Game (IOI13_game) C++11
100 / 100
 5435 ms 87920 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "game.h"
//#include "grader.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long int ll;
int R, C;

ll gcd(ll x, ll y) {
	if (x == 0 || y == 0) return max(x, y);
	return __gcd(x, y);
}

struct nodeY
{
	int lo, hi;
	nodeY *l=0, *r=0;
	ll val = 0;
};

struct nodeX {
	nodeX *l=0, *r=0;
	nodeY *root=0;
	nodeX() {
		l = 0, r = 0;
		root = new nodeY();
		root->lo = 0, root->hi = C - 1;
	}
};
nodeX *root=0;

ll qry2(nodeY *cur, int yL, int yH) {
	if (!cur) return 0;
	if (yH < cur->lo || cur->hi < yL) return 0;
	if (yL <= cur->lo && cur->hi <= yH) return cur->val;
	return gcd(qry2(cur->l, yL, yH), qry2(cur->r, yL, yH));
}

ll qry1(nodeX *cur, int l, int r, int xL, int xH, int yL, int yH) {
	if (!cur) return 0;
	if (r < xL || xH < l) return 0;
	if (xL <= l && r <= xH) return qry2(cur->root, yL, yH);
	int m = (l + r) / 2;
	return gcd(qry1(cur->l, l, m, xL, xH, yL, yH), qry1(cur->r, m+1, r, xL, xH, yL, yH));
} 

void upd2(nodeY *cur, int y, ll val) {
	if (cur->lo == cur->hi) {
		cur->val = val;
		return;
	}
	int m = (cur->lo + cur->hi) / 2;
	nodeY *&nxt = (y <= m) ? cur->l : cur->r;
	if (!nxt) {
		nxt = new nodeY();
		nxt->lo = y, nxt->hi = y;
		nxt->val = val;
	} else if (nxt->lo <= y && y <= nxt->hi)
		upd2(nxt, y, val);
	else {
		nodeY *nx = new nodeY();
		nx->lo = cur->lo, nx->hi = cur->hi;
		do {
			if (y <= m)
				nx->hi = m;
			else
				nx->lo = m + 1;
			m = (nx->lo + nx->hi) / 2;
		} while ((y <= m) == (nxt->lo <= m));
		if (y <= m)
			nx->r = nxt;
		else
			nx->l = nxt;
		nxt = nx;
		upd2(nx, y, val);
	}
	ll a = 0, b = 0;
	if (cur->l) a = cur->l->val;
	if (cur->r) b = cur->r->val;
	cur->val = gcd(a, b);
}

void upd1(int l, int r, nodeX *cur, int x, int y, ll val) {
	if (l == r) {
		upd2(cur->root, y, val);
		return;
	}
	int m = (l + r) / 2;
	ll a = 0, b = 0;
	if (x <= m) {
		if (!cur->l) cur->l = new nodeX();
		upd1(l, m, cur->l, x, y, val);
	} else {
		if (!cur->r) cur->r = new nodeX();
		upd1(m+1, r, cur->r, x, y, val);
	}
	if (cur->l) a = qry2(cur->l->root, y, y);
	if (cur->r) b = qry2(cur->r->root, y, y);
	upd2(cur->root, y, gcd(a, b));
}

void init(int R1, int C1) {
	R = R1, C = C1;
	root = new nodeX();
}

void update(int p, int q, ll k) {
	upd1(0, R-1, root, p, q, k);
}

ll calculate(int p, int q, int u, int v) {
	return qry1(root, 0, R-1, 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 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 736 ms 12932 KB Output is correct
5 Correct 553 ms 12532 KB Output is correct
6 Correct 761 ms 10252 KB Output is correct
7 Correct 942 ms 9836 KB Output is correct
8 Correct 504 ms 8056 KB Output is correct
9 Correct 755 ms 10000 KB Output is correct
10 Correct 801 ms 9740 KB Output is correct
11 Correct 2 ms 512 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 400 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 368 KB Output is correct
12 Correct 1285 ms 15720 KB Output is correct
13 Correct 2537 ms 9036 KB Output is correct
14 Correct 333 ms 5756 KB Output is correct
15 Correct 2924 ms 10756 KB Output is correct
16 Correct 289 ms 14240 KB Output is correct
17 Correct 1075 ms 11220 KB Output is correct
18 Correct 2476 ms 15836 KB Output is correct
19 Correct 2071 ms 15828 KB Output is correct
20 Correct 1952 ms 15256 KB Output is correct
21 Correct 2 ms 384 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 2 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 2 ms 356 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 3 ms 400 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 687 ms 12856 KB Output is correct
13 Correct 536 ms 12584 KB Output is correct
14 Correct 686 ms 10060 KB Output is correct
15 Correct 779 ms 9876 KB Output is correct
16 Correct 476 ms 8248 KB Output is correct
17 Correct 714 ms 9984 KB Output is correct
18 Correct 713 ms 9580 KB Output is correct
19 Correct 1304 ms 15576 KB Output is correct
20 Correct 2500 ms 8940 KB Output is correct
21 Correct 268 ms 5704 KB Output is correct
22 Correct 2688 ms 10940 KB Output is correct
23 Correct 337 ms 14364 KB Output is correct
24 Correct 1341 ms 11448 KB Output is correct
25 Correct 2820 ms 15820 KB Output is correct
26 Correct 2327 ms 15964 KB Output is correct
27 Correct 1980 ms 15420 KB Output is correct
28 Correct 879 ms 46200 KB Output is correct
29 Correct 2187 ms 48288 KB Output is correct
30 Correct 3807 ms 36996 KB Output is correct
31 Correct 3711 ms 29912 KB Output is correct
32 Correct 455 ms 10236 KB Output is correct
33 Correct 686 ms 10856 KB Output is correct
34 Correct 503 ms 42104 KB Output is correct
35 Correct 1952 ms 28632 KB Output is correct
36 Correct 4162 ms 46104 KB Output is correct
37 Correct 2918 ms 46356 KB Output is correct
38 Correct 3138 ms 45708 KB Output is correct
39 Correct 2231 ms 37848 KB Output is correct
40 Correct 2 ms 384 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 836 ms 12688 KB Output is correct
13 Correct 549 ms 12576 KB Output is correct
14 Correct 759 ms 10116 KB Output is correct
15 Correct 914 ms 9848 KB Output is correct
16 Correct 468 ms 8184 KB Output is correct
17 Correct 891 ms 10128 KB Output is correct
18 Correct 796 ms 9672 KB Output is correct
19 Correct 1297 ms 15736 KB Output is correct
20 Correct 2621 ms 9000 KB Output is correct
21 Correct 331 ms 5624 KB Output is correct
22 Correct 3050 ms 10872 KB Output is correct
23 Correct 292 ms 14200 KB Output is correct
24 Correct 1314 ms 11452 KB Output is correct
25 Correct 2562 ms 15872 KB Output is correct
26 Correct 2035 ms 16064 KB Output is correct
27 Correct 2015 ms 15268 KB Output is correct
28 Correct 741 ms 46076 KB Output is correct
29 Correct 2260 ms 48132 KB Output is correct
30 Correct 4244 ms 37008 KB Output is correct
31 Correct 3756 ms 29756 KB Output is correct
32 Correct 420 ms 10232 KB Output is correct
33 Correct 655 ms 10796 KB Output is correct
34 Correct 470 ms 42000 KB Output is correct
35 Correct 1798 ms 28452 KB Output is correct
36 Correct 3755 ms 46268 KB Output is correct
37 Correct 2784 ms 46472 KB Output is correct
38 Correct 2731 ms 45920 KB Output is correct
39 Correct 960 ms 86968 KB Output is correct
40 Correct 3582 ms 87920 KB Output is correct
41 Correct 5435 ms 70768 KB Output is correct
42 Correct 5039 ms 55104 KB Output is correct
43 Correct 965 ms 82720 KB Output is correct
44 Correct 610 ms 10760 KB Output is correct
45 Correct 2357 ms 38064 KB Output is correct
46 Correct 5045 ms 86752 KB Output is correct
47 Correct 4585 ms 86868 KB Output is correct
48 Correct 4944 ms 86552 KB Output is correct
49 Correct 3 ms 404 KB Output is correct