oj.uz

Submission #100359

# Submission time Handle Problem Language Result Execution time Memory
100359 2019-03-10T14:08:51 Z jhnah917 Game (IOI13_game) C++14
0 / 100
 4 ms 384 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;
	}
};
 
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);
			T t = l->seg->query(y, y);
			if(r) t = f(t, r->seg->query(y, y));
			if(!seg) seg = new Seg1d();
			seg->update(y, v);
		}else{
			if(!r) r = new Seg2d();
			r->update(x, y, v, m+1, e);
			T t = r->seg->query(y, y);
			if(l) t = f(t, l->seg->query(y, y));
			if(!seg) seg = new Seg1d();
			seg->update(y, v);
		}
	}
	
	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 Seg2d::update(int, int, T, int, int)':
game.cpp:83: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:106:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s + e >> 1;
           ~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 3 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 3 ms 384 KB Output isn't correct
3 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 Incorrect 4 ms 384 KB Output isn't correct
3 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 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -