oj.uz

Submission #122087

# Submission time Handle Problem Language Result Execution time Memory
122087 2019-06-27T14:19:10 Z ekrem Game (IOI13_game) C++
63 / 100
 2600 ms 15352 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 sol (k+k)
#define sag (k+k+1)
#define mod 1000000007
#define MAXN 1000005
using namespace std;
// #define fail(s, x...) do { \
// 		fprintf(stderr, s "\n", ## x); \
// 		exit(1); \
// 	} while(0)


typedef long long ll;

int n, m, son, seg[4*MAXN], sl[4*MAXN], sg[4*MAXN];
ll vl[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){
	return (!seg[k])?seg[k] = ++son:seg[k];
}

int solver(int k){
	return (!sl[k])?sl[k] = ++son:sl[k];
}

int sagver(int k){
	return (!sg[k])?sg[k] = ++son:sg[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 vl[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(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, bas, orta, x, y, xx, yy), qu1(sag, orta + 1, son, x, y, xx, yy));
}

void up2(int k, int bas, int son, int x, ll z){
	if(bas == son){
		vl[k] = z;
		return;
	}
	if(x <= orta)
		up2(solver(k), bas, orta, x, z);
	else
		up2(sagver(k), orta + 1, son, x, z);
	vl[k] = gcd2(vl[sl[k]], vl[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(sol, bas, orta, x, y, z);
	else
		up1(sag, orta + 1, son, x, y, z);
	z = gcd2(qu2(ver(sol), 1, m, y, y), qu2(ver(sag), 1, m, y, y));
	up2(ver(k), 1, m, y, z);
}

void init(int R, int C) {
	n = R;m = C;
}

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:13: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 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 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 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 574 ms 12696 KB Output is correct
5 Correct 383 ms 12600 KB Output is correct
6 Correct 603 ms 9876 KB Output is correct
7 Correct 777 ms 9848 KB Output is correct
8 Correct 452 ms 8444 KB Output is correct
9 Correct 938 ms 9936 KB Output is correct
10 Correct 582 ms 9336 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 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 356 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 908 ms 14020 KB Output is correct
13 Correct 2252 ms 7216 KB Output is correct
14 Correct 373 ms 5272 KB Output is correct
15 Correct 2585 ms 8204 KB Output is correct
16 Correct 237 ms 12628 KB Output is correct
17 Correct 1173 ms 10908 KB Output is correct
18 Correct 2165 ms 14328 KB Output is correct
19 Correct 1838 ms 14840 KB Output is correct
20 Correct 1381 ms 13944 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 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 2 ms 384 KB Output is correct
10 Correct 3 ms 380 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 591 ms 12836 KB Output is correct
13 Correct 380 ms 12536 KB Output is correct
14 Correct 660 ms 9564 KB Output is correct
15 Correct 812 ms 9376 KB Output is correct
16 Correct 460 ms 8248 KB Output is correct
17 Correct 750 ms 9380 KB Output is correct
18 Correct 642 ms 8824 KB Output is correct
19 Correct 907 ms 14124 KB Output is correct
20 Correct 2121 ms 6564 KB Output is correct
21 Correct 314 ms 4600 KB Output is correct
22 Correct 2555 ms 8588 KB Output is correct
23 Correct 225 ms 12768 KB Output is correct
24 Correct 1060 ms 10984 KB Output is correct
25 Correct 2169 ms 14800 KB Output is correct
26 Correct 1549 ms 14944 KB Output is correct
27 Correct 1538 ms 14108 KB Output is correct
28 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.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 3 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 591 ms 12880 KB Output is correct
13 Correct 398 ms 12536 KB Output is correct
14 Correct 685 ms 10396 KB Output is correct
15 Correct 807 ms 9980 KB Output is correct
16 Correct 473 ms 8676 KB Output is correct
17 Correct 788 ms 10060 KB Output is correct
18 Correct 694 ms 9668 KB Output is correct
19 Correct 884 ms 14200 KB Output is correct
20 Correct 2232 ms 7624 KB Output is correct
21 Correct 325 ms 5640 KB Output is correct
22 Correct 2600 ms 9336 KB Output is correct
23 Correct 266 ms 13692 KB Output is correct
24 Correct 1165 ms 11320 KB Output is correct
25 Correct 2296 ms 15352 KB Output is correct
26 Correct 1860 ms 14772 KB Output is correct
27 Correct 1669 ms 14428 KB Output is correct
28 Runtime error 4 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -