oj.uz

Submission #96816

# Submission time Handle Problem Language Result Execution time Memory
96816 2019-02-12T08:52:04 Z jhnah917 Game (IOI13_game) C++14
0 / 100
 155 ms 140252 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;
	return f(ysum(xnode, ynode*2, ys, ym, yl, yr), ysum(xnode, ynode*2+1, ym+1, ye, yl, yr));
}

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;
	return f(xsum(xnode*2, xs, xm, xl, xr, yl, yr), xsum(xnode*2+1, xm+1, xe, xl, xr, yl, yr));
}

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 h = (int)ceil(log2(n+1))+1;
    tree = new T*[1 << h];
    for(int i=0; i<(1<<h); i++){
    	h = (int)ceil(log2(m+1))+1;
    	tree[i] = new T[1 << h];
    	for(int j=0; j<(1<<h); 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Runtime error 155 ms 140252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 4 ms 1024 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 896 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Runtime error 3 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 4 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 896 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Runtime error 3 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 4 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 4 ms 768 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Runtime error 3 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -