oj.uz

Submission #122109

# Submission time Handle Problem Language Result Execution time Memory
122109 2019-06-27T14:44:46 Z ekrem Game (IOI13_game) C++
80 / 100
 5508 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 60000005
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)
		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 640 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 7 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 552 ms 10032 KB Output is correct
5 Correct 378 ms 10104 KB Output is correct
6 Correct 644 ms 7232 KB Output is correct
7 Correct 721 ms 6876 KB Output is correct
8 Correct 455 ms 5652 KB Output is correct
9 Correct 731 ms 7100 KB Output is correct
10 Correct 631 ms 6680 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 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 412 KB Output is correct
7 Correct 2 ms 356 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 911 ms 11280 KB Output is correct
13 Correct 2192 ms 5208 KB Output is correct
14 Correct 296 ms 2444 KB Output is correct
15 Correct 2699 ms 7356 KB Output is correct
16 Correct 244 ms 12024 KB Output is correct
17 Correct 1177 ms 8568 KB Output is correct
18 Correct 2303 ms 12264 KB Output is correct
19 Correct 1920 ms 12072 KB Output is correct
20 Correct 1800 ms 11896 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 3 ms 384 KB Output is correct
4 Correct 2 ms 512 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 612 ms 9632 KB Output is correct
13 Correct 390 ms 9848 KB Output is correct
14 Correct 667 ms 7496 KB Output is correct
15 Correct 790 ms 7288 KB Output is correct
16 Correct 485 ms 5780 KB Output is correct
17 Correct 766 ms 7544 KB Output is correct
18 Correct 631 ms 7176 KB Output is correct
19 Correct 909 ms 11344 KB Output is correct
20 Correct 2124 ms 5872 KB Output is correct
21 Correct 309 ms 3064 KB Output is correct
22 Correct 2586 ms 6880 KB Output is correct
23 Correct 231 ms 11844 KB Output is correct
24 Correct 1230 ms 8264 KB Output is correct
25 Correct 2237 ms 11680 KB Output is correct
26 Correct 1849 ms 11976 KB Output is correct
27 Correct 1514 ms 11524 KB Output is correct
28 Correct 905 ms 127576 KB Output is correct
29 Correct 2362 ms 142340 KB Output is correct
30 Correct 5508 ms 103604 KB Output is correct
31 Correct 5078 ms 79772 KB Output is correct
32 Correct 596 ms 2756 KB Output is correct
33 Correct 805 ms 4088 KB Output is correct
34 Correct 592 ms 139384 KB Output is correct
35 Correct 2004 ms 72112 KB Output is correct
36 Correct 3944 ms 140044 KB Output is correct
37 Correct 3236 ms 140124 KB Output is correct
38 Correct 3063 ms 139372 KB Output is correct
39 Correct 2601 ms 108072 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 2 ms 488 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 2 ms 384 KB Output is correct
12 Correct 592 ms 9744 KB Output is correct
13 Correct 394 ms 9848 KB Output is correct
14 Correct 625 ms 6796 KB Output is correct
15 Correct 712 ms 6520 KB Output is correct
16 Correct 433 ms 5644 KB Output is correct
17 Correct 686 ms 6708 KB Output is correct
18 Correct 562 ms 6264 KB Output is correct
19 Correct 865 ms 11356 KB Output is correct
20 Correct 2120 ms 4868 KB Output is correct
21 Correct 295 ms 2168 KB Output is correct
22 Correct 2537 ms 6272 KB Output is correct
23 Correct 230 ms 10744 KB Output is correct
24 Correct 1106 ms 7860 KB Output is correct
25 Correct 2086 ms 11220 KB Output is correct
26 Correct 1799 ms 11936 KB Output is correct
27 Correct 1423 ms 11256 KB Output is correct
28 Correct 855 ms 127352 KB Output is correct
29 Correct 2141 ms 142200 KB Output is correct
30 Correct 5088 ms 102276 KB Output is correct
31 Correct 4767 ms 78300 KB Output is correct
32 Correct 548 ms 1272 KB Output is correct
33 Correct 741 ms 2552 KB Output is correct
34 Correct 580 ms 137820 KB Output is correct
35 Correct 1954 ms 70556 KB Output is correct
36 Correct 3967 ms 138360 KB Output is correct
37 Correct 3067 ms 138488 KB Output is correct
38 Correct 2938 ms 137956 KB Output is correct
39 Runtime error 1346 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -