oj.uz

Submission #122117

# Submission time Handle Problem Language Result Execution time Memory
122117 2019-06-27T14:54:48 Z ekrem Game (IOI13_game) C++
80 / 100
 6279 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 80000005
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;
vector < int > sol, sag, seg, sl, sg;
vector < ll > val;

ll opr(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;
	sl.pb(0), sg.pb(0),val.pb(0);
	return (!seg[k])?seg[k] = ++son:seg[k];
}

int slver(int k){
	sl.pb(0), sg.pb(0),val.pb(0);
	return (!sl[k])?sl[k] = ++son:sl[k];
}

int sgver(int k){
	sl.pb(0), sg.pb(0),val.pb(0);
	return (!sg[k])?sg[k] = ++son:sg[k];
}

int solver(int k){
	sol.pb(0), sag.pb(0), seg.pb(0);
	return (!sol[k])?sol[k] = ++son1:sol[k];
}

int sagver(int k){
	sol.pb(0), sag.pb(0), seg.pb(0);
	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 opr(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 opr(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] = opr(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 = opr(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++;
	sol.pb(0), sag.pb(0), seg.pb(0), sl.pb(0), sg.pb(0),val.pb(0);
	sol.pb(0), sag.pb(0), seg.pb(0), sl.pb(0), sg.pb(0),val.pb(0);
	sol.pb(0), sag.pb(0), seg.pb(0), sl.pb(0), sg.pb(0),val.pb(0);
	sol.pb(0), sag.pb(0), seg.pb(0), sl.pb(0), sg.pb(0),val.pb(0);
}

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 512 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 512 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 284 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 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 654 ms 19028 KB Output is correct
5 Correct 446 ms 19216 KB Output is correct
6 Correct 669 ms 16224 KB Output is correct
7 Correct 785 ms 15892 KB Output is correct
8 Correct 490 ms 9444 KB Output is correct
9 Correct 769 ms 16040 KB Output is correct
10 Correct 683 ms 15588 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 512 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 2 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 1014 ms 30536 KB Output is correct
13 Correct 2307 ms 27016 KB Output is correct
14 Correct 373 ms 28660 KB Output is correct
15 Correct 2683 ms 29596 KB Output is correct
16 Correct 310 ms 29512 KB Output is correct
17 Correct 1275 ms 15488 KB Output is correct
18 Correct 2289 ms 29992 KB Output is correct
19 Correct 1836 ms 30160 KB Output is correct
20 Correct 1658 ms 29388 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 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 428 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 3 ms 512 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 657 ms 19024 KB Output is correct
13 Correct 471 ms 19312 KB Output is correct
14 Correct 655 ms 16272 KB Output is correct
15 Correct 798 ms 16020 KB Output is correct
16 Correct 451 ms 9376 KB Output is correct
17 Correct 743 ms 15936 KB Output is correct
18 Correct 615 ms 15660 KB Output is correct
19 Correct 1020 ms 30592 KB Output is correct
20 Correct 2289 ms 26928 KB Output is correct
21 Correct 369 ms 28360 KB Output is correct
22 Correct 2725 ms 29456 KB Output is correct
23 Correct 297 ms 29380 KB Output is correct
24 Correct 1395 ms 15648 KB Output is correct
25 Correct 2291 ms 29968 KB Output is correct
26 Correct 1760 ms 30128 KB Output is correct
27 Correct 1588 ms 29316 KB Output is correct
28 Correct 1264 ms 202624 KB Output is correct
29 Correct 2705 ms 206332 KB Output is correct
30 Correct 6279 ms 202684 KB Output is correct
31 Correct 5447 ms 202540 KB Output is correct
32 Correct 1036 ms 202004 KB Output is correct
33 Correct 1263 ms 201856 KB Output is correct
34 Correct 940 ms 201828 KB Output is correct
35 Correct 2194 ms 103972 KB Output is correct
36 Correct 4655 ms 203012 KB Output is correct
37 Correct 3542 ms 204260 KB Output is correct
38 Correct 3513 ms 203960 KB Output is correct
39 Correct 2825 ms 126400 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 512 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 2 ms 512 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 651 ms 19508 KB Output is correct
13 Correct 516 ms 19812 KB Output is correct
14 Correct 706 ms 16732 KB Output is correct
15 Correct 795 ms 16392 KB Output is correct
16 Correct 453 ms 9792 KB Output is correct
17 Correct 718 ms 16556 KB Output is correct
18 Correct 597 ms 16092 KB Output is correct
19 Correct 1080 ms 31068 KB Output is correct
20 Correct 2423 ms 26904 KB Output is correct
21 Correct 387 ms 28912 KB Output is correct
22 Correct 2791 ms 30096 KB Output is correct
23 Correct 336 ms 29920 KB Output is correct
24 Correct 1184 ms 16036 KB Output is correct
25 Correct 2212 ms 30360 KB Output is correct
26 Correct 1860 ms 30572 KB Output is correct
27 Correct 1493 ms 29900 KB Output is correct
28 Correct 1281 ms 203588 KB Output is correct
29 Correct 2576 ms 206528 KB Output is correct
30 Correct 5761 ms 202856 KB Output is correct
31 Correct 5481 ms 202728 KB Output is correct
32 Correct 1037 ms 201924 KB Output is correct
33 Correct 1293 ms 201868 KB Output is correct
34 Correct 976 ms 202096 KB Output is correct
35 Correct 2287 ms 103908 KB Output is correct
36 Correct 4596 ms 202936 KB Output is correct
37 Correct 3792 ms 204280 KB Output is correct
38 Correct 3600 ms 203548 KB Output is correct
39 Runtime error 1348 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -