oj.uz

답안 #122421

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122421 2019-06-28T07:41:41 Z ekrem 게임 (IOI13_game) C++
100 / 100
 7440 ms 49600 KB 
#include <bits/stdc++.h>
#include "game.h"
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas+son)/2)
#define oorta ((bbas+sson)/2)
#define mod 1000000007
#define MAXN 20000005
using namespace std;
// #define fail(s, x...) do { \
// 		fprintf(stderr, s "\n", ## x); \
// 		exit(1); \
// 	} while(0)
 
 
typedef long long ll;
 
int n, m, son1, son2, sol[MAXN], sag[MAXN], seg[MAXN], sl[MAXN], sg[MAXN], bas[MAXN], son[MAXN];
ll val[MAXN];
 
ll gcd2(ll X, ll Y) {
    if(X == 0 || Y == 0) {
        return X + Y;
    }
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
 
 
int ver(int k){
	if(!k)return 0;
	if(!seg[k]){
		son2++;
		bas[son2] = 1;
		son[son2] = m;
		return seg[k] = son2;
	}
	else
		return seg[k];
}

int yeniver(int bs, int sn){
	++son2;
	bas[son2]=bs;
	son[son2]=sn;
	return son2;
}
 
int slver(int k){
	return (!sl[k])?sl[k] = ++son2:sl[k];
}
 
int sgver(int k){
	return (!sg[k])?sg[k] = ++son2:sg[k];
}
 
int solver(int k){
	return (!sol[k])?sol[k] = ++son1:sol[k];
}
 
int sagver(int k){
	return (!sag[k])?sag[k] = ++son1:sag[k];
}
 
ll qu2(int k, int x, int y){
	if(!k or bas[k] > y or son[k] < x)
		return 0;
	if(bas[k] >= x and son[k] <= y)
		return val[k];
	return gcd2(qu2(sl[k], x, y), qu2(sg[k], x, y));
}
 
ll qu1(int k, int bas, int son, int x, int y, int xx, int yy){
	if(!k or bas > y or son < x)
		return 0;
	if(bas >= x and son <= y)
		return qu2(seg[k], xx, yy);
	return gcd2(qu1(sol[k], bas, orta, x, y, xx, yy), qu1(sag[k], orta + 1, son, x, y, xx, yy));
}
 
void up2(int k, int x, ll z){
	if(bas[k] == son[k]){
		val[k] = z;
		return;
	}
	int git = (x <= ((bas[k]+son[k])/2)) ? sl[k] : sg[k];
	if(!git){
		int of = ((x <= ((bas[k]+son[k])/2)) ? sl[k] : sg[k]) = yeniver(x, x);
		val[of] = z;
	}
	else if(bas[git] <= x and son[git] >= x)
			up2(git, x, z);
	else{
		int	bbas = bas[k], sson = son[k];
		do{
			if(x <= oorta)
				sson = oorta;
			else
				bbas = oorta + 1;
		}while((x <= oorta) == (bas[git] <= oorta) );
		int of = ((x <= ((bas[k]+son[k])/2)) ? sl[k] : sg[k]) = yeniver(bbas, sson);
		(bas[git] <= oorta ? sl[of] : sg[of]) = git;
		up2(of, x, z);
	}
	val[k] = gcd2(val[sl[k]], val[sg[k]]);
}
 
void up1(int k, int bas, int son, int x, int y, ll z){
	if(bas == son){
		up2(ver(k), y, z);
		return;
	}
	if(x <= orta)
		up1(solver(k), bas, orta, x, y, z);
	else
		up1(sagver(k), orta + 1, son, x, y, z);
	z = gcd2(qu2(seg[sol[k]], y, y), qu2(seg[sag[k]], y, y));
	up2(ver(k), y, z);
}
 
void init(int R, int C) {
	n = R;m = C;
	son1++;
}
 
void update(int p, int q, ll k) {
  up1(1, 1, n, p + 1, q + 1, k);
}
 
ll calculate(int p, int q, int u, int v) {
  return qu1(1, 1, n, p+1, u+1, q+1, v+1);
}
 
// int main() {
// 	int R, C, N;
//     int P, Q, U, V;
//     long long K;
//     int i, type;
// 	int res;
 
// 	FILE *f = fopen("in.txt", "r");
// 	if (!f)
// 		fail("Failed to open input file.");
 
// 	res = fscanf(f, "%d", &R);
// 	res = fscanf(f, "%d", &C);
// 	res = fscanf(f, "%d", &N);
 
//     init(R, C);
 
// 	for (i = 0; i < N; i++) {
//         res = fscanf(f, "%d", &type);
//         if (type == 1) {
// 		    res = fscanf(f, "%d%d%lld", &P, &Q, &K);
//             update(P, Q, K);
//         } else if (type == 2) {
// 		    res = fscanf(f, "%d%d%d%d", &P, &Q, &U, &V);
//             printf("%lld\n", calculate(P, Q, U, V));
//         } else
// 			fail("Invalid action type in input file.");
// 	}
// 	fclose(f);
 
// 	return 0;
// }

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:12:1: warning: multi-line comment [-Wcomment]
 // #define fail(s, x...) do { \
 ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 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 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 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 2 ms 384 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 633 ms 8756 KB Output is correct
5 Correct 375 ms 9080 KB Output is correct
6 Correct 679 ms 6020 KB Output is correct
7 Correct 702 ms 5624 KB Output is correct
8 Correct 447 ms 5412 KB Output is correct
9 Correct 776 ms 5752 KB Output is correct
10 Correct 640 ms 5368 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 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 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 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1070 ms 10300 KB Output is correct
13 Correct 2554 ms 5368 KB Output is correct
14 Correct 264 ms 3212 KB Output is correct
15 Correct 2959 ms 6184 KB Output is correct
16 Correct 217 ms 7800 KB Output is correct
17 Correct 1002 ms 6288 KB Output is correct
18 Correct 2131 ms 8160 KB Output is correct
19 Correct 1705 ms 8540 KB Output is correct
20 Correct 1488 ms 7812 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 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 356 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 643 ms 8876 KB Output is correct
13 Correct 377 ms 9080 KB Output is correct
14 Correct 681 ms 5880 KB Output is correct
15 Correct 729 ms 5624 KB Output is correct
16 Correct 430 ms 5236 KB Output is correct
17 Correct 755 ms 5584 KB Output is correct
18 Correct 644 ms 5240 KB Output is correct
19 Correct 1190 ms 10292 KB Output is correct
20 Correct 2947 ms 5560 KB Output is correct
21 Correct 273 ms 3204 KB Output is correct
22 Correct 3135 ms 6136 KB Output is correct
23 Correct 230 ms 7932 KB Output is correct
24 Correct 1086 ms 6268 KB Output is correct
25 Correct 2107 ms 8268 KB Output is correct
26 Correct 1624 ms 8360 KB Output is correct
27 Correct 1314 ms 7836 KB Output is correct
28 Correct 577 ms 19960 KB Output is correct
29 Correct 1952 ms 22776 KB Output is correct
30 Correct 4381 ms 17068 KB Output is correct
31 Correct 3692 ms 13688 KB Output is correct
32 Correct 403 ms 2860 KB Output is correct
33 Correct 563 ms 3192 KB Output is correct
34 Correct 320 ms 19416 KB Output is correct
35 Correct 1388 ms 12004 KB Output is correct
36 Correct 3317 ms 19652 KB Output is correct
37 Correct 2172 ms 20088 KB Output is correct
38 Correct 2420 ms 19320 KB Output is correct
39 Correct 2094 ms 16248 KB Output is correct
40 Correct 2 ms 384 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 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 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 2 ms 428 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 654 ms 7964 KB Output is correct
13 Correct 415 ms 8280 KB Output is correct
14 Correct 619 ms 5220 KB Output is correct
15 Correct 706 ms 4956 KB Output is correct
16 Correct 403 ms 4600 KB Output is correct
17 Correct 673 ms 5008 KB Output is correct
18 Correct 626 ms 4600 KB Output is correct
19 Correct 1186 ms 9780 KB Output is correct
20 Correct 2840 ms 4852 KB Output is correct
21 Correct 293 ms 2936 KB Output is correct
22 Correct 3258 ms 6296 KB Output is correct
23 Correct 269 ms 8172 KB Output is correct
24 Correct 1098 ms 6648 KB Output is correct
25 Correct 2110 ms 8608 KB Output is correct
26 Correct 1496 ms 8680 KB Output is correct
27 Correct 1336 ms 7928 KB Output is correct
28 Correct 726 ms 20140 KB Output is correct
29 Correct 1842 ms 22612 KB Output is correct
30 Correct 4440 ms 17152 KB Output is correct
31 Correct 3786 ms 13804 KB Output is correct
32 Correct 403 ms 3160 KB Output is correct
33 Correct 606 ms 3488 KB Output is correct
34 Correct 333 ms 19444 KB Output is correct
35 Correct 1328 ms 11872 KB Output is correct
36 Correct 2837 ms 19948 KB Output is correct
37 Correct 2264 ms 19756 KB Output is correct
38 Correct 2227 ms 19364 KB Output is correct
39 Correct 934 ms 47864 KB Output is correct
40 Correct 3608 ms 49600 KB Output is correct
41 Correct 7440 ms 38772 KB Output is correct
42 Correct 5924 ms 31108 KB Output is correct
43 Correct 779 ms 44060 KB Output is correct
44 Correct 491 ms 10592 KB Output is correct
45 Correct 1771 ms 24416 KB Output is correct
46 Correct 4145 ms 48312 KB Output is correct
47 Correct 4495 ms 48204 KB Output is correct
48 Correct 4187 ms 47804 KB Output is correct
49 Correct 2 ms 384 KB Output is correct