oj.uz

Submission #100271

# Submission time Handle Problem Language Result Execution time Memory
100271 2019-03-10T07:43:54 Z jhnah917 Game (IOI13_game) C++14
63 / 100
 3131 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;
	
	void update(int x, int y, T v, int s = 0, int e = R-1){
		if(s == x && x == e){
			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);
		}
		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(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:93: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:108: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 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 384 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 2 ms 384 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 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 777 ms 16992 KB Output is correct
5 Correct 435 ms 16888 KB Output is correct
6 Correct 878 ms 14588 KB Output is correct
7 Correct 997 ms 14404 KB Output is correct
8 Correct 660 ms 10792 KB Output is correct
9 Correct 1073 ms 14336 KB Output is correct
10 Correct 721 ms 13892 KB Output is correct
11 Correct 3 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 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 256 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 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1062 ms 19832 KB Output is correct
13 Correct 2475 ms 10024 KB Output is correct
14 Correct 341 ms 5672 KB Output is correct
15 Correct 2914 ms 13064 KB Output is correct
16 Correct 288 ms 22264 KB Output is correct
17 Correct 1583 ms 16412 KB Output is correct
18 Correct 2554 ms 23800 KB Output is correct
19 Correct 2353 ms 23908 KB Output is correct
20 Correct 2349 ms 23420 KB Output is correct
21 Correct 3 ms 384 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 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 3 ms 356 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 797 ms 17016 KB Output is correct
13 Correct 464 ms 16608 KB Output is correct
14 Correct 794 ms 14440 KB Output is correct
15 Correct 963 ms 14292 KB Output is correct
16 Correct 600 ms 10872 KB Output is correct
17 Correct 967 ms 14356 KB Output is correct
18 Correct 898 ms 13988 KB Output is correct
19 Correct 1150 ms 19932 KB Output is correct
20 Correct 2523 ms 10200 KB Output is correct
21 Correct 357 ms 5724 KB Output is correct
22 Correct 3053 ms 13020 KB Output is correct
23 Correct 288 ms 22316 KB Output is correct
24 Correct 1570 ms 16368 KB Output is correct
25 Correct 3131 ms 23824 KB Output is correct
26 Correct 2555 ms 24244 KB Output is correct
27 Correct 2422 ms 23272 KB Output is correct
28 Runtime error 1425 ms 257024 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 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 3 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 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 796 ms 16928 KB Output is correct
13 Correct 559 ms 16824 KB Output is correct
14 Correct 878 ms 14408 KB Output is correct
15 Correct 929 ms 14280 KB Output is correct
16 Correct 669 ms 10864 KB Output is correct
17 Correct 1162 ms 14340 KB Output is correct
18 Correct 995 ms 13880 KB Output is correct
19 Correct 1153 ms 19768 KB Output is correct
20 Correct 2556 ms 10108 KB Output is correct
21 Correct 319 ms 5564 KB Output is correct
22 Correct 2968 ms 13156 KB Output is correct
23 Correct 279 ms 22380 KB Output is correct
24 Correct 1685 ms 16404 KB Output is correct
25 Correct 2955 ms 23960 KB Output is correct
26 Correct 2453 ms 24056 KB Output is correct
27 Correct 2174 ms 23544 KB Output is correct
28 Runtime error 1423 ms 257024 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
29 Halted 0 ms 0 KB -