oj.uz

답안 #104913

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
104913 2019-04-09T15:55:23 Z eriksuenderhauf 게임 (IOI13_game) C++11
63 / 100
 3198 ms 257024 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;
	if (y <= m) {
		if (!cur->l) {
			cur->l = new nodeY();
			cur->l->lo = cur->lo;
			cur->l->hi = m;
			cur->l->val = val;
		}
		upd2(cur->l, y, val);
	} else {
		if (!cur->r) {
			cur->r = new nodeY();
			cur->r->lo = m + 1;
			cur->r->hi = cur->hi;
			cur->r->val = val;
		}
		upd2(cur->r, 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

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

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 911 ms 17840 KB Output is correct
5 Correct 616 ms 18152 KB Output is correct
6 Correct 836 ms 15352 KB Output is correct
7 Correct 973 ms 14992 KB Output is correct
8 Correct 491 ms 10160 KB Output is correct
9 Correct 950 ms 15032 KB Output is correct
10 Correct 940 ms 14608 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1624 ms 22552 KB Output is correct
13 Correct 2755 ms 9968 KB Output is correct
14 Correct 373 ms 2120 KB Output is correct
15 Correct 3073 ms 13808 KB Output is correct
16 Correct 355 ms 27816 KB Output is correct
17 Correct 1717 ms 17460 KB Output is correct
18 Correct 3073 ms 28120 KB Output is correct
19 Correct 2545 ms 28500 KB Output is correct
20 Correct 2383 ms 27768 KB Output is correct
21 Correct 3 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 858 ms 17816 KB Output is correct
13 Correct 593 ms 18232 KB Output is correct
14 Correct 773 ms 15248 KB Output is correct
15 Correct 909 ms 14968 KB Output is correct
16 Correct 639 ms 10212 KB Output is correct
17 Correct 1040 ms 14996 KB Output is correct
18 Correct 886 ms 14872 KB Output is correct
19 Correct 1498 ms 22648 KB Output is correct
20 Correct 2594 ms 9884 KB Output is correct
21 Correct 328 ms 2168 KB Output is correct
22 Correct 3032 ms 13632 KB Output is correct
23 Correct 366 ms 27760 KB Output is correct
24 Correct 1607 ms 17552 KB Output is correct
25 Correct 2970 ms 28376 KB Output is correct
26 Correct 2538 ms 28500 KB Output is correct
27 Correct 2495 ms 27932 KB Output is correct
28 Runtime error 960 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 751 ms 17980 KB Output is correct
13 Correct 582 ms 18272 KB Output is correct
14 Correct 833 ms 15480 KB Output is correct
15 Correct 1026 ms 15088 KB Output is correct
16 Correct 608 ms 10332 KB Output is correct
17 Correct 941 ms 15352 KB Output is correct
18 Correct 923 ms 14648 KB Output is correct
19 Correct 1360 ms 22476 KB Output is correct
20 Correct 2747 ms 9808 KB Output is correct
21 Correct 379 ms 2012 KB Output is correct
22 Correct 3057 ms 13660 KB Output is correct
23 Correct 337 ms 27844 KB Output is correct
24 Correct 1567 ms 17552 KB Output is correct
25 Correct 3198 ms 28056 KB Output is correct
26 Correct 2620 ms 28168 KB Output is correct
27 Correct 2510 ms 27752 KB Output is correct
28 Runtime error 938 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -