oj.uz

Submission #100355

# Submission time Handle Problem Language Result Execution time Memory
100355 2019-03-10T14:03:06 Z jhnah917 Game (IOI13_game) C++14
63 / 100
 3095 ms 257024 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 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 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 380 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 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 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 727 ms 12628 KB Output is correct
5 Correct 481 ms 13016 KB Output is correct
6 Correct 819 ms 9812 KB Output is correct
7 Correct 899 ms 9664 KB Output is correct
8 Correct 574 ms 6712 KB Output is correct
9 Correct 1012 ms 9852 KB Output is correct
10 Correct 793 ms 9368 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 2 ms 384 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 284 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 1136 ms 15820 KB Output is correct
13 Correct 2373 ms 6284 KB Output is correct
14 Correct 425 ms 1044 KB Output is correct
15 Correct 2878 ms 8816 KB Output is correct
16 Correct 275 ms 18428 KB Output is correct
17 Correct 1549 ms 11456 KB Output is correct
18 Correct 2665 ms 18644 KB Output is correct
19 Correct 2325 ms 18748 KB Output is correct
20 Correct 2303 ms 18124 KB Output is correct
21 Correct 2 ms 300 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 4 ms 384 KB Output is correct
3 Correct 3 ms 356 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 4 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 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 793 ms 12568 KB Output is correct
13 Correct 446 ms 12972 KB Output is correct
14 Correct 915 ms 9864 KB Output is correct
15 Correct 917 ms 9684 KB Output is correct
16 Correct 522 ms 6632 KB Output is correct
17 Correct 867 ms 9792 KB Output is correct
18 Correct 759 ms 9380 KB Output is correct
19 Correct 1158 ms 15736 KB Output is correct
20 Correct 2427 ms 6208 KB Output is correct
21 Correct 373 ms 1060 KB Output is correct
22 Correct 2835 ms 8876 KB Output is correct
23 Correct 251 ms 20316 KB Output is correct
24 Correct 1804 ms 11532 KB Output is correct
25 Correct 3028 ms 18652 KB Output is correct
26 Correct 2378 ms 18880 KB Output is correct
27 Correct 2400 ms 18156 KB Output is correct
28 Correct 1521 ms 251584 KB Output is correct
29 Runtime error 2837 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 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 2 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 3 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 757 ms 12672 KB Output is correct
13 Correct 502 ms 12964 KB Output is correct
14 Correct 908 ms 9980 KB Output is correct
15 Correct 935 ms 9552 KB Output is correct
16 Correct 525 ms 6740 KB Output is correct
17 Correct 832 ms 9796 KB Output is correct
18 Correct 812 ms 9356 KB Output is correct
19 Correct 1035 ms 15836 KB Output is correct
20 Correct 2587 ms 6388 KB Output is correct
21 Correct 360 ms 932 KB Output is correct
22 Correct 3095 ms 8816 KB Output is correct
23 Correct 326 ms 18236 KB Output is correct
24 Correct 1707 ms 11548 KB Output is correct
25 Correct 2873 ms 18636 KB Output is correct
26 Correct 2417 ms 18736 KB Output is correct
27 Correct 2207 ms 18112 KB Output is correct
28 Correct 1446 ms 251792 KB Output is correct
29 Runtime error 2687 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -