Submission #100356

#	Time	Username	Problem	Language	Result	Execution time	Memory
100356		jhnah917	Game (IOI13_game)	C++14	63 / 100	3020 ms	256544 KiB

game

#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 (stderr)

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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20