oj.uz

Submission #100356

# Submission time Handle Problem Language Result Execution time Memory
100356 2019-03-10T14:03:06 Z jhnah917 Game (IOI13_game) C++14
63 / 100
 3020 ms 256544 KB 
#ifndef __GAME_H__
#define __GAME_H__
 
#ifdef __cplusplus
extern "C" {
#endif
 
#include <math.h>
#include <stdio.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 R, C;
 
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;
 
struct Seg1d{
	T val;
	Seg1d *l, *r;
	
	Seg1d(){
		val = 0;
		l = r = NULL;
	}
	
	void update(int x, T v, int s = 0, int e = C-1){
		if(s == x && x == e){
			val = v; return;
		}
		
		int m = s + e >> 1;
		if(x <= m){
			if(!l) l = new Seg1d();
			l->update(x, v, s, m);
		}else{
			if(!r) r = new Seg1d();
			r->update(x, v, m+1, e);
		}
		
		val = 0;
		if(l) val = f(val, l->val);
		if(r) val = f(val, r->val);
	}
	
	T query(int L, int R, int s = 0, int e = C-1){
		if(R < s || e < L) return 0;
		if(L <= s && e <= R) return val;
		
		int m = s + e >> 1;
		T ret = 0;
		if(l) ret = f(ret, l->query(L, R, s, m));
		if(r) ret = f(ret, r->query(L, R, m+1, e));
		return ret;
	}
	
	void update2(int idx, Seg1d *a, Seg1d *b, int s = 0, int e = C-1){
		if(s != e){
			int m = s + e >> 1;
			if(idx <= m){
				if(!l) l = new Seg1d();
				l->update2(idx, a ? a->l : NULL, b ? b->l : NULL, s, m);
			}else{
				if(!r) r = new Seg1d();
				r->update2(idx, a ? a->r : NULL, b ? b->r : NULL, m+1, e);
			}
		}
		val = 0;
		if(a) val = f(val, a->val);
		if(b) val = f(val, b->val);
	}
};
 
struct Seg2d{
	Seg1d *seg;
	Seg2d *l, *r;
	
	Seg2d(){
		seg = NULL;
		l = r = NULL;
	}
	
	void update(int x, int y, T v, int s = 0, int e = R-1){
		if(s == x && x == e){
			if(!seg) seg = new Seg1d();
			seg->update(y, v); return;
		}
		
		int m = s + e >> 1;
		if(x <= m){
			if(!l) l = new Seg2d();
			l->update(x, y, v, s, m);
		}else{
			if(!r) r = new Seg2d();
			r->update(x, y, v, m+1, e);
		}
		if(!seg) seg = new Seg1d();
		seg->update2(y, l ? l->seg : NULL, r ? r->seg : NULL);
	}
	
	T query(int x1, int x2, int y1, int y2, int s = 0, int e = R-1){
		if(!seg) return 0;
		if(x1 <= s && e <= x2) return seg->query(y1, y2);
		if(x2 < s || e < x1) return 0;
		
		int m = s + e >> 1;
		T ret = 0;
		if(l) ret = f(ret, l->query(x1, x2, y1, y2, s, m));
		if(r) ret = f(ret, r->query(x1, x2, y1, y2, m+1, e));
		return ret;
	}
} tree;
 
 
void init(int r, int c) {
	R = r, C = c;
}
 
void update(int x, int y, long long val) {
	tree.update(x, y, val);
}
 
long long calculate(int x1, int y1, int x2, int y2) {
    return tree.query(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;
      ^~~
game.cpp: In member function 'void Seg1d::update(int, T, int, int)':
game.cpp:42:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s + e >> 1;
           ~~^~~
game.cpp: In member function 'T Seg1d::query(int, int, int, int)':
game.cpp:60:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s + e >> 1;
           ~~^~~
game.cpp: In member function 'void Seg1d::update2(int, Seg1d*, Seg1d*, int, int)':
game.cpp:69:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int m = s + e >> 1;
            ~~^~~
game.cpp: In member function 'void Seg2d::update(int, int, T, int, int)':
game.cpp:99:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s + e >> 1;
           ~~^~~
game.cpp: In member function 'T Seg2d::query(int, int, int, int, int, int)':
game.cpp:116:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s + e >> 1;
           ~~^~~

Subtask #1
10.0 / 10.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 356 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 3 ms 384 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 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 754 ms 14700 KB Output is correct
5 Correct 457 ms 14924 KB Output is correct
6 Correct 835 ms 12032 KB Output is correct
7 Correct 875 ms 11808 KB Output is correct
8 Correct 640 ms 8808 KB Output is correct
9 Correct 824 ms 11860 KB Output is correct
10 Correct 773 ms 11380 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 256 KB Output is correct
2 Correct 3 ms 428 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 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 432 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 284 KB Output is correct
12 Correct 1066 ms 17956 KB Output is correct
13 Correct 2482 ms 8412 KB Output is correct
14 Correct 345 ms 3104 KB Output is correct
15 Correct 2877 ms 10868 KB Output is correct
16 Correct 329 ms 20472 KB Output is correct
17 Correct 1653 ms 13808 KB Output is correct
18 Correct 2726 ms 20752 KB Output is correct
19 Correct 2398 ms 21012 KB Output is correct
20 Correct 2255 ms 20244 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 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 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 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 857 ms 14848 KB Output is correct
13 Correct 546 ms 14988 KB Output is correct
14 Correct 875 ms 12104 KB Output is correct
15 Correct 967 ms 11868 KB Output is correct
16 Correct 555 ms 8716 KB Output is correct
17 Correct 843 ms 11884 KB Output is correct
18 Correct 697 ms 11472 KB Output is correct
19 Correct 1165 ms 17964 KB Output is correct
20 Correct 2586 ms 8404 KB Output is correct
21 Correct 326 ms 3036 KB Output is correct
22 Correct 2976 ms 11088 KB Output is correct
23 Correct 249 ms 18208 KB Output is correct
24 Correct 1723 ms 13540 KB Output is correct
25 Correct 2913 ms 20616 KB Output is correct
26 Correct 2216 ms 20868 KB Output is correct
27 Correct 2278 ms 20116 KB Output is correct
28 Runtime error 1587 ms 256464 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 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 256 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 256 KB Output is correct
9 Correct 3 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 843 ms 15352 KB Output is correct
13 Correct 493 ms 15608 KB Output is correct
14 Correct 806 ms 12760 KB Output is correct
15 Correct 947 ms 12428 KB Output is correct
16 Correct 580 ms 9380 KB Output is correct
17 Correct 936 ms 12472 KB Output is correct
18 Correct 842 ms 11996 KB Output is correct
19 Correct 1126 ms 18492 KB Output is correct
20 Correct 2310 ms 8864 KB Output is correct
21 Correct 341 ms 3636 KB Output is correct
22 Correct 3020 ms 11608 KB Output is correct
23 Correct 301 ms 20952 KB Output is correct
24 Correct 1557 ms 14268 KB Output is correct
25 Correct 2948 ms 21376 KB Output is correct
26 Correct 2376 ms 21604 KB Output is correct
27 Correct 2256 ms 20976 KB Output is correct
28 Runtime error 1427 ms 256544 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
29 Halted 0 ms 0 KB -