oj.uz

Submission #122102

# Submission time Handle Problem Language Result Execution time Memory
122102 2019-06-27T14:39:55 Z ekrem Game (IOI13_game) C++
80 / 100
 5577 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 30000005
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 3 ms 512 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 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 2 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 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 582 ms 8696 KB Output is correct
5 Correct 390 ms 8824 KB Output is correct
6 Correct 695 ms 5804 KB Output is correct
7 Correct 834 ms 5496 KB Output is correct
8 Correct 423 ms 4368 KB Output is correct
9 Correct 700 ms 5636 KB Output is correct
10 Correct 576 ms 5360 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 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 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 875 ms 10300 KB Output is correct
13 Correct 2131 ms 3728 KB Output is correct
14 Correct 297 ms 1224 KB Output is correct
15 Correct 2495 ms 5240 KB Output is correct
16 Correct 231 ms 9720 KB Output is correct
17 Correct 1121 ms 6776 KB Output is correct
18 Correct 2222 ms 10212 KB Output is correct
19 Correct 1876 ms 10280 KB Output is correct
20 Correct 1565 ms 9564 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 3 ms 384 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 4 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 554 ms 8540 KB Output is correct
13 Correct 370 ms 8908 KB Output is correct
14 Correct 620 ms 5880 KB Output is correct
15 Correct 792 ms 5624 KB Output is correct
16 Correct 466 ms 4408 KB Output is correct
17 Correct 776 ms 5508 KB Output is correct
18 Correct 621 ms 5368 KB Output is correct
19 Correct 951 ms 10212 KB Output is correct
20 Correct 2239 ms 4008 KB Output is correct
21 Correct 312 ms 988 KB Output is correct
22 Correct 2709 ms 4992 KB Output is correct
23 Correct 246 ms 9720 KB Output is correct
24 Correct 1063 ms 6720 KB Output is correct
25 Correct 2044 ms 10108 KB Output is correct
26 Correct 1834 ms 10360 KB Output is correct
27 Correct 1458 ms 9692 KB Output is correct
28 Correct 911 ms 125804 KB Output is correct
29 Correct 2320 ms 140888 KB Output is correct
30 Correct 5577 ms 102136 KB Output is correct
31 Correct 5168 ms 78296 KB Output is correct
32 Correct 577 ms 1116 KB Output is correct
33 Correct 803 ms 2424 KB Output is correct
34 Correct 612 ms 137924 KB Output is correct
35 Correct 2180 ms 70392 KB Output is correct
36 Correct 4204 ms 138360 KB Output is correct
37 Correct 3269 ms 138292 KB Output is correct
38 Correct 3161 ms 138072 KB Output is correct
39 Correct 2728 ms 106368 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 384 KB Output is correct
2 Correct 2 ms 384 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 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 556 ms 8564 KB Output is correct
13 Correct 371 ms 8824 KB Output is correct
14 Correct 614 ms 5752 KB Output is correct
15 Correct 740 ms 5532 KB Output is correct
16 Correct 434 ms 4544 KB Output is correct
17 Correct 697 ms 5676 KB Output is correct
18 Correct 547 ms 5112 KB Output is correct
19 Correct 1046 ms 10268 KB Output is correct
20 Correct 2261 ms 3744 KB Output is correct
21 Correct 300 ms 1024 KB Output is correct
22 Correct 2588 ms 5052 KB Output is correct
23 Correct 244 ms 9716 KB Output is correct
24 Correct 1156 ms 6752 KB Output is correct
25 Correct 2189 ms 10160 KB Output is correct
26 Correct 1931 ms 10176 KB Output is correct
27 Correct 1475 ms 9524 KB Output is correct
28 Correct 862 ms 125548 KB Output is correct
29 Correct 2267 ms 141128 KB Output is correct
30 Correct 5169 ms 103244 KB Output is correct
31 Correct 5030 ms 79420 KB Output is correct
32 Correct 551 ms 2708 KB Output is correct
33 Correct 763 ms 3992 KB Output is correct
34 Correct 593 ms 139776 KB Output is correct
35 Correct 2064 ms 72148 KB Output is correct
36 Correct 3896 ms 140208 KB Output is correct
37 Correct 3224 ms 140276 KB Output is correct
38 Correct 2928 ms 139844 KB Output is correct
39 Runtime error 1293 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -