oj.uz

Submission #96819

# Submission time Handle Problem Language Result Execution time Memory
96819 2019-02-12T09:15:47 Z jhnah917 Game (IOI13_game) C++14
63 / 100
 3701 ms 129332 KB 
#ifndef __GAME_H__
#define __GAME_H__

#ifdef __cplusplus
extern "C" {
#endif

#include <math.h>

void init(int R, int C);
void update(int P, int Q, long long K);
long long calculate(int P, int Q, int U, int V);
int n, m;

long long f(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

typedef long long T;

T **tree;

T ysum(int xnode, int ynode, int ys, int ye, int yl, int yr){
	if(yr < ys || ye < yl) return 0;
	if(yl <= ys && ye <= yr) return tree[xnode][ynode];
	int ym = (ys + ye) >> 1;
	T ret = 0;
	if(ys <= ym) ret = f(ret, ysum(xnode, ynode*2, ys, ym, yl, yr));
	if(ym+1 <= ye) ret = f(ret, ysum(xnode, ynode*2+1, ym+1, ye, yl, yr));
	return ret;
}

T xsum(int xnode, int xs, int xe, int xl, int xr, int yl, int yr){
	if(xr < xs || xe < xl) return 0;
	if(xl <= xs && xe <= xr) return ysum(xnode, 1, 0, m-1, yl, yr);
	int xm = (xs + xe) >> 1;
	T ret = 0;
	if(xs <= xm) ret = f(ret, xsum(xnode*2, xs, xm, xl, xr, yl, yr));
	if(xm+1 <= xe) ret = f(ret, xsum(xnode*2+1, xm+1, xe, xl, xr, yl, yr));
	return ret;
}

void yupdate(int xnode, int xs, int xe, int ynode, int ys, int ye, int x, int y, T val){
	if(ye < y || y < ys) return;
	if(ys^ye){
		int ym = (ys + ye) >> 1;
		if(y <= ym) yupdate(xnode, xs, xe, ynode*2, ys, ym, x, y, val);
		else yupdate(xnode, xs, xe, ynode*2+1, ym+1, ye, x, y, val);
		
		tree[xnode][ynode] = f(tree[xnode][ynode*2], tree[xnode][ynode*2+1]);
	}else{
		if(xs^xe) tree[xnode][ynode] = f(tree[xnode*2][ynode], tree[xnode*2+1][ynode]);
		else tree[xnode][ynode] = val;
	}
}

void xupdate(int xnode, int xs, int xe, int x, int y, T val){
	if(xe < x || x < xs) return;
	if(xs^xe){
		int xm = (xs + xe) >> 1;
		if(x <= xm) xupdate(xnode*2, xs, xm, x, y, val);
		else xupdate(xnode*2+1, xm+1, xe, x, y, val);
	}
	yupdate(xnode, xs, xe, 1, 0, m-1, x, y, val);
}

void init(int R, int C) {
	n = R, m = C;
	int u = 1, v = 1;
	while(u < n) u <<= 1;
	while(v < m) v <<= 1;
	u = u*2+5, v = v*2+5;
	tree = new T*[u];
	for(int i=0; i<u; i++){
		tree[i] = new T[v];
		for(int j=0; j<m; j++) tree[i][j] = 0LL;
	}
}

void update(int x, int y, long long val) {
    xupdate(1, 0, n-1, x, y, val);
}

long long calculate(int x1, int y1, int x2, int y2) {
    return xsum(1, 0, n-1, x1, x2, y1, y2);
}

#ifdef __cplusplus
}
#endif

#endif /* __GAME_H__ */

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;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 3 ms 896 KB Output is correct
12 Correct 2 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 1164 ms 59076 KB Output is correct
5 Correct 703 ms 59100 KB Output is correct
6 Correct 1079 ms 58616 KB Output is correct
7 Correct 1022 ms 58360 KB Output is correct
8 Correct 782 ms 56360 KB Output is correct
9 Correct 984 ms 58360 KB Output is correct
10 Correct 911 ms 58164 KB Output is correct
11 Correct 2 ms 256 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 768 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 896 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 3 ms 768 KB Output is correct
11 Correct 3 ms 896 KB Output is correct
12 Correct 1305 ms 41276 KB Output is correct
13 Correct 2482 ms 33156 KB Output is correct
14 Correct 912 ms 87160 KB Output is correct
15 Correct 3083 ms 95612 KB Output is correct
16 Correct 464 ms 127384 KB Output is correct
17 Correct 2268 ms 119132 KB Output is correct
18 Correct 3140 ms 129332 KB Output is correct
19 Correct 3044 ms 128796 KB Output is correct
20 Correct 2833 ms 128208 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 3 ms 816 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 2 ms 896 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 1169 ms 58940 KB Output is correct
13 Correct 654 ms 59000 KB Output is correct
14 Correct 1018 ms 58656 KB Output is correct
15 Correct 997 ms 58300 KB Output is correct
16 Correct 836 ms 56384 KB Output is correct
17 Correct 1004 ms 58360 KB Output is correct
18 Correct 890 ms 57928 KB Output is correct
19 Correct 1310 ms 41308 KB Output is correct
20 Correct 2457 ms 33292 KB Output is correct
21 Correct 1082 ms 86944 KB Output is correct
22 Correct 3203 ms 95768 KB Output is correct
23 Correct 1353 ms 127252 KB Output is correct
24 Correct 2266 ms 119008 KB Output is correct
25 Correct 3168 ms 129268 KB Output is correct
26 Correct 2726 ms 128904 KB Output is correct
27 Correct 2560 ms 128100 KB Output is correct
28 Runtime error 3 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 3 ms 384 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 2 ms 896 KB Output is correct
11 Correct 3 ms 896 KB Output is correct
12 Correct 1095 ms 58992 KB Output is correct
13 Correct 663 ms 58968 KB Output is correct
14 Correct 977 ms 58712 KB Output is correct
15 Correct 1006 ms 58316 KB Output is correct
16 Correct 749 ms 56344 KB Output is correct
17 Correct 1012 ms 58340 KB Output is correct
18 Correct 917 ms 57952 KB Output is correct
19 Correct 1371 ms 41212 KB Output is correct
20 Correct 2545 ms 33200 KB Output is correct
21 Correct 1792 ms 86860 KB Output is correct
22 Correct 3060 ms 95556 KB Output is correct
23 Correct 1047 ms 127352 KB Output is correct
24 Correct 2227 ms 118968 KB Output is correct
25 Correct 3701 ms 129056 KB Output is correct
26 Correct 2836 ms 128900 KB Output is correct
27 Correct 2312 ms 128248 KB Output is correct
28 Runtime error 48 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -