oj.uz

Submission #122098

# Submission time Handle Problem Language Result Execution time Memory
122098 2019-06-27T14:37:10 Z ekrem Game (IOI13_game) C++
80 / 100
 5429 ms 207532 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 10000005
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[4*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)
		up2(slver(k), bas, orta, x, 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 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 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 3 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

# 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 2 ms 384 KB Output is correct
4 Correct 555 ms 8576 KB Output is correct
5 Correct 379 ms 8800 KB Output is correct
6 Correct 648 ms 5880 KB Output is correct
7 Correct 735 ms 5496 KB Output is correct
8 Correct 429 ms 4500 KB Output is correct
9 Correct 786 ms 5776 KB Output is correct
10 Correct 647 ms 5316 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 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 2 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 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 869 ms 10108 KB Output is correct
13 Correct 2228 ms 3828 KB Output is correct
14 Correct 310 ms 1016 KB Output is correct
15 Correct 2594 ms 5064 KB Output is correct
16 Correct 238 ms 9860 KB Output is correct
17 Correct 1094 ms 6648 KB Output is correct
18 Correct 2077 ms 10232 KB Output is correct
19 Correct 1786 ms 10420 KB Output is correct
20 Correct 1590 ms 9648 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 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 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 634 ms 8516 KB Output is correct
13 Correct 379 ms 8720 KB Output is correct
14 Correct 629 ms 5672 KB Output is correct
15 Correct 722 ms 5388 KB Output is correct
16 Correct 408 ms 4412 KB Output is correct
17 Correct 712 ms 5548 KB Output is correct
18 Correct 591 ms 5116 KB Output is correct
19 Correct 892 ms 10112 KB Output is correct
20 Correct 2155 ms 3708 KB Output is correct
21 Correct 300 ms 1020 KB Output is correct
22 Correct 2557 ms 5080 KB Output is correct
23 Correct 237 ms 9752 KB Output is correct
24 Correct 1064 ms 6584 KB Output is correct
25 Correct 2064 ms 10048 KB Output is correct
26 Correct 1778 ms 10444 KB Output is correct
27 Correct 1576 ms 9704 KB Output is correct
28 Correct 961 ms 125696 KB Output is correct
29 Correct 2314 ms 146912 KB Output is correct
30 Correct 5429 ms 107968 KB Output is correct
31 Correct 4823 ms 83996 KB Output is correct
32 Correct 553 ms 6904 KB Output is correct
33 Correct 777 ms 8184 KB Output is correct
34 Correct 608 ms 143864 KB Output is correct
35 Correct 2023 ms 76064 KB Output is correct
36 Correct 4390 ms 143788 KB Output is correct
37 Correct 3247 ms 144000 KB Output is correct
38 Correct 3056 ms 143488 KB Output is correct
39 Correct 2644 ms 112016 KB Output is correct
40 Correct 2 ms 384 KB Output is correct

Subtask #5
0 / 20.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 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 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 559 ms 8460 KB Output is correct
13 Correct 376 ms 8752 KB Output is correct
14 Correct 598 ms 5672 KB Output is correct
15 Correct 726 ms 5464 KB Output is correct
16 Correct 430 ms 4408 KB Output is correct
17 Correct 734 ms 5496 KB Output is correct
18 Correct 547 ms 5068 KB Output is correct
19 Correct 913 ms 10060 KB Output is correct
20 Correct 2127 ms 3700 KB Output is correct
21 Correct 293 ms 1000 KB Output is correct
22 Correct 2518 ms 4992 KB Output is correct
23 Correct 236 ms 9720 KB Output is correct
24 Correct 1184 ms 6704 KB Output is correct
25 Correct 2017 ms 10148 KB Output is correct
26 Correct 1642 ms 10292 KB Output is correct
27 Correct 1437 ms 9688 KB Output is correct
28 Correct 879 ms 125688 KB Output is correct
29 Correct 2247 ms 145752 KB Output is correct
30 Correct 5206 ms 107012 KB Output is correct
31 Correct 4793 ms 83124 KB Output is correct
32 Correct 575 ms 5908 KB Output is correct
33 Correct 1028 ms 7336 KB Output is correct
34 Correct 620 ms 143036 KB Output is correct
35 Correct 2049 ms 75200 KB Output is correct
36 Correct 4050 ms 143044 KB Output is correct
37 Correct 3113 ms 143152 KB Output is correct
38 Correct 3039 ms 142536 KB Output is correct
39 Incorrect 1963 ms 207532 KB Output isn't correct
40 Halted 0 ms 0 KB -