oj.uz

Submission #122095

# Submission time Handle Problem Language Result Execution time Memory
122095 2019-06-27T14:35:26 Z ekrem Game (IOI13_game) C++
63 / 100
 2585 ms 103500 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 5000005
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 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 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 3 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 594 ms 9308 KB Output is correct
5 Correct 389 ms 9336 KB Output is correct
6 Correct 704 ms 6648 KB Output is correct
7 Correct 795 ms 6392 KB Output is correct
8 Correct 443 ms 4856 KB Output is correct
9 Correct 689 ms 6648 KB Output is correct
10 Correct 544 ms 6264 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 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 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 877 ms 10676 KB Output is correct
13 Correct 2211 ms 4600 KB Output is correct
14 Correct 307 ms 1912 KB Output is correct
15 Correct 2554 ms 5880 KB Output is correct
16 Correct 229 ms 10616 KB Output is correct
17 Correct 1200 ms 7568 KB Output is correct
18 Correct 2094 ms 11060 KB Output is correct
19 Correct 1898 ms 11228 KB Output is correct
20 Correct 1518 ms 10464 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
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 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 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 552 ms 8972 KB Output is correct
13 Correct 369 ms 9244 KB Output is correct
14 Correct 611 ms 6380 KB Output is correct
15 Correct 714 ms 6112 KB Output is correct
16 Correct 426 ms 5100 KB Output is correct
17 Correct 1016 ms 6236 KB Output is correct
18 Correct 650 ms 5804 KB Output is correct
19 Correct 918 ms 10564 KB Output is correct
20 Correct 2181 ms 4444 KB Output is correct
21 Correct 295 ms 1664 KB Output is correct
22 Correct 2585 ms 5664 KB Output is correct
23 Correct 245 ms 10488 KB Output is correct
24 Correct 1076 ms 7368 KB Output is correct
25 Correct 2201 ms 10752 KB Output is correct
26 Correct 1953 ms 10856 KB Output is correct
27 Correct 1425 ms 10360 KB Output is correct
28 Incorrect 1212 ms 103500 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 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 593 ms 9040 KB Output is correct
13 Correct 395 ms 9240 KB Output is correct
14 Correct 659 ms 6264 KB Output is correct
15 Correct 762 ms 5964 KB Output is correct
16 Correct 505 ms 4856 KB Output is correct
17 Correct 651 ms 6044 KB Output is correct
18 Correct 523 ms 5460 KB Output is correct
19 Correct 921 ms 10744 KB Output is correct
20 Correct 2278 ms 4216 KB Output is correct
21 Correct 308 ms 1400 KB Output is correct
22 Correct 2462 ms 5472 KB Output is correct
23 Correct 234 ms 10104 KB Output is correct
24 Correct 1028 ms 7028 KB Output is correct
25 Correct 2141 ms 10500 KB Output is correct
26 Correct 1793 ms 10732 KB Output is correct
27 Correct 1378 ms 10232 KB Output is correct
28 Incorrect 1199 ms 102520 KB Output isn't correct
29 Halted 0 ms 0 KB -