oj.uz

Submission #122404

# Submission time Handle Problem Language Result Execution time Memory
122404 2019-06-28T07:15:00 Z ekrem Game (IOI13_game) C++
80 / 100
 5465 ms 256000 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 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, son, sol[MAXN], sag[MAXN], seg[MAXN], sl[MAXN], sg[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;
	return (!seg[k])?seg[k] = ++son:seg[k];
}
 
int slver(int k){
	return (!sl[k])?sl[k] = ++son:sl[k];
}
 
int sgver(int k){
	return (!sg[k])?sg[k] = ++son: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 bas, int son, int x, int y){
	if(!k or bas > y or son < x)
		return 0;
	if(bas >= x and son <= y)
		return val[k];
	return gcd2(qu2(sl[k], bas, orta, x, y), qu2(sg[k], orta + 1, son, 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], 1, m, 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 bas, int son, int x, ll z){
	if(bas == son){
		val[k] = z;
		return;
	}
	if(x <= orta){
		if(!sl[k]){
			int kk = slver(k);
			int bbas = bas, sson = orta;
			while(bbas < sson){
				val[kk] = z;
				if(x <= ((bbas+sson)/2))
					kk = slver(kk), sson = ((bbas+sson)/2);
				else
					kk = sgver(kk), bbas = ((bbas+sson)/2) + 1;
			}
			val[kk] = z;
		} else
			up2(slver(k), bas, orta, x, z);
	}
	else{
		if(!sg[k]){
			int kk = sgver(k);
			int bbas = orta + 1, sson = son;
			while(bbas < sson){
				val[kk] = z;
				if(x <= ((bbas+sson)/2))
					kk = slver(kk), sson = ((bbas+sson)/2);
				else
					kk = sgver(kk), bbas = ((bbas+sson)/2) + 1;
			}
			val[kk] = z;
		} else
			up2(sgver(k), orta + 1, son, 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), 1, m, 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(ver(sol[k]), 1, m, y, y), qu2(ver(sag[k]), 1, m, y, y));
	up2(ver(k), 1, m, 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:11:1: warning: multi-line comment [-Wcomment]
 // #define fail(s, x...) do { \
 ^

Subtask #1
10.0 / 10.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 3 ms 384 KB Output is correct
5 Correct 3 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 3 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 3 ms 384 KB Output is correct
12 Correct 2 ms 356 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 2 ms 384 KB Output is correct
4 Correct 596 ms 12860 KB Output is correct
5 Correct 383 ms 12664 KB Output is correct
6 Correct 633 ms 10140 KB Output is correct
7 Correct 757 ms 9984 KB Output is correct
8 Correct 414 ms 8364 KB Output is correct
9 Correct 676 ms 10104 KB Output is correct
10 Correct 607 ms 9620 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
26.0 / 26.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 2 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 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 915 ms 13972 KB Output is correct
13 Correct 2375 ms 7432 KB Output is correct
14 Correct 328 ms 5520 KB Output is correct
15 Correct 2600 ms 9248 KB Output is correct
16 Correct 255 ms 13688 KB Output is correct
17 Correct 1140 ms 11256 KB Output is correct
18 Correct 2017 ms 15328 KB Output is correct
19 Correct 1608 ms 15392 KB Output is correct
20 Correct 1492 ms 14732 KB Output is correct
21 Correct 3 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory 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 256 KB Output is correct
6 Correct 2 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 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 598 ms 13020 KB Output is correct
13 Correct 388 ms 12508 KB Output is correct
14 Correct 606 ms 10232 KB Output is correct
15 Correct 753 ms 9976 KB Output is correct
16 Correct 478 ms 8536 KB Output is correct
17 Correct 736 ms 10104 KB Output is correct
18 Correct 623 ms 9748 KB Output is correct
19 Correct 1124 ms 14072 KB Output is correct
20 Correct 2181 ms 7424 KB Output is correct
21 Correct 341 ms 5496 KB Output is correct
22 Correct 2677 ms 9288 KB Output is correct
23 Correct 260 ms 13816 KB Output is correct
24 Correct 1152 ms 11392 KB Output is correct
25 Correct 2086 ms 15476 KB Output is correct
26 Correct 2135 ms 15436 KB Output is correct
27 Correct 1660 ms 14784 KB Output is correct
28 Correct 1148 ms 136312 KB Output is correct
29 Correct 2081 ms 150776 KB Output is correct
30 Correct 5465 ms 108776 KB Output is correct
31 Correct 4989 ms 84884 KB Output is correct
32 Correct 586 ms 10092 KB Output is correct
33 Correct 811 ms 11272 KB Output is correct
34 Correct 555 ms 144500 KB Output is correct
35 Correct 2051 ms 79952 KB Output is correct
36 Correct 4134 ms 148732 KB Output is correct
37 Correct 3515 ms 148644 KB Output is correct
38 Correct 3128 ms 148372 KB Output is correct
39 Correct 2598 ms 116340 KB Output is correct
40 Correct 3 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory 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 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 412 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 566 ms 12704 KB Output is correct
13 Correct 380 ms 12660 KB Output is correct
14 Correct 608 ms 10336 KB Output is correct
15 Correct 724 ms 9976 KB Output is correct
16 Correct 449 ms 8444 KB Output is correct
17 Correct 772 ms 10160 KB Output is correct
18 Correct 657 ms 9748 KB Output is correct
19 Correct 1004 ms 14328 KB Output is correct
20 Correct 2186 ms 7464 KB Output is correct
21 Correct 300 ms 5624 KB Output is correct
22 Correct 2508 ms 9336 KB Output is correct
23 Correct 227 ms 13740 KB Output is correct
24 Correct 1107 ms 11256 KB Output is correct
25 Correct 2033 ms 15260 KB Output is correct
26 Correct 1858 ms 15368 KB Output is correct
27 Correct 1593 ms 14712 KB Output is correct
28 Correct 856 ms 135724 KB Output is correct
29 Correct 2312 ms 150916 KB Output is correct
30 Correct 5275 ms 108716 KB Output is correct
31 Correct 5059 ms 84928 KB Output is correct
32 Correct 591 ms 10360 KB Output is correct
33 Correct 841 ms 11520 KB Output is correct
34 Correct 672 ms 144604 KB Output is correct
35 Correct 2017 ms 80124 KB Output is correct
36 Correct 4144 ms 148772 KB Output is correct
37 Correct 3240 ms 148940 KB Output is correct
38 Correct 3145 ms 148488 KB Output is correct
39 Runtime error 1397 ms 256000 KB Execution failed because the return code was nonzero
40 Halted 0 ms 0 KB -