| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 99541 |
2019-03-04T21:50:52 Z |
jhnah917 |
Game (IOI13_game) |
C++14 |
|
2 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;
}
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;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
