| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 98935 |
2019-02-27T15:22:36 Z |
jhnah917 |
Game (IOI13_game) |
C++14 |
|
4 ms |
896 KB |
#ifndef __GAME_H__
#define __GAME_H__
#ifdef __cplusplus
extern "C" {
#endif
#include <math.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;
typedef long long ll;
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;
}
struct Seg1d{
ll *arr;
Seg1d(){
int h = (int)ceil(log2(c+1))+1;
int size = 1<<h;
arr = new ll[size];
for(int i=0; i<size; i++) arr[i] = 0;
}
void update(int node, int s, int e, int y, ll val){
if(e < y || y < s) return;
if(s == e){
arr[node] = val; return;
}
int m = s + e >> 1;
if(y <= m) update(node*2, s, m, y, val);
else update(node*2+1, m+1, e, y, val);
arr[node] = f(arr[node*2], arr[node*2+1]);
}
ll query(int node, int s, int e, int l, int r){
if(r < s || e < l) return 0;
if(l <= s && e <= r) return arr[node];
int m = s + e >> 1;
return f(query(node*2, s, m, l, r), query(node*2+1, m+1, e, l, r));
}
};
struct Seg2d{
Seg1d *arr;
Seg2d(){
int h = (int)ceil(log2(r+1))+1;
int size = 1<<h;
arr = new Seg1d[size];
}
void update(int node, int s, int e, int x, int y, ll val){
if(e < x || x < s) return;
if(s == e){
arr[node].update(1, 0, c-1, y, val); return;
}
int m = s + e >> 1;
if(x <= m) update(node*2, s, m, x, y, val);
else update(node*2+1, m+1, e, x, y, val);
arr[node].update(1, 0, c-1, y, val);
}
ll query(int node, int s, int e, int x1, int x2, int y1, int y2){
if(x2 < s || e < x1) return 0;
if(x1 <= s && e <= x2) return arr[node].query(1, 0, c-1, y1, y2);
int m = s + e >> 1;
ll t1 = query(node*2, s, m, x1, x2, y1, y2);
ll t2 = query(node*2+1, m+1, e, x1, x2, y1, y2);
return f(t1, t2);
}
} tree;
void init(int R, int C) {
r = R, c = C;
tree = Seg2d();
}
void update(int x, int y, long long val) {
tree.update(1, 0, r-1, x, y, val);
}
long long calculate(int x1, int y1, int x2, int y2) {
return tree.query(1, 0, r-1, 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, int, int, int, ll)':
game.cpp:42:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s + e >> 1;
~~^~~
game.cpp: In member function 'll Seg1d::query(int, int, int, int, int)':
game.cpp:50:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s + e >> 1;
~~^~~
game.cpp: In member function 'void Seg2d::update(int, int, int, int, int, ll)':
game.cpp:69:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s + e >> 1;
~~^~~
game.cpp: In member function 'll Seg2d::query(int, int, int, int, int, int, int)':
game.cpp:78:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s + e >> 1;
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
896 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
896 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
