| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 37984 |
2017-12-29T21:19:31 Z |
alenam0161 |
Game (IOI13_game) |
C++14 |
|
0 ms |
1844 KB |
#include "game.h"
#include <algorithm>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int N = ((int)1 << 30) - 1;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct node {
long long val;
node *lup, *ldown, *rup, *rdown;
node(long long q = 0) {
val = q;
lup = ldown = rup = rdown = NULL;
}
};
node *root;
node* get_node() {
static node T[7000 * 1000];
static int counter = 0;
return &T[counter++];
}
inline long long get_(node *t) {
return t ? t->val : 0ll;
}
inline bool in_(int llx, int lly, int rrx, int rry, int nx, int ny) {
return (llx <= nx&&lly <= ny&&rrx >= nx&&rry >= ny);
}
inline bool in_rect(int llx, int lly, int rrx, int rry, int nlx, int nly, int nrx, int nry) {
return (nrx < llx || nry < lly || rrx < nlx || rry < nly) ? 0 : 1;
}
void init(int R, int C) {
/* ... */
}
void updatequard(int x, int y, long long val, node *&t, int nlx, int nly, int nrx, int nry) {
if (!t)t = get_node();
if (nlx == nrx&&nry == nly) {
t->val = val;
return;
}
int mx = (nlx + nrx) / 2;
int my = (nly + nry) / 2;
if (in_(nlx, nly, mx, my, x, y))updatequard(x, y, val, t->ldown, nlx, nly, mx, my);
else if (in_(mx + 1, nly, nrx, my, x, y))updatequard(x, y, val, t->lup, mx + 1, nly, nrx, my);
else if (in_(nlx, my + 1, mx, nry, x, y))updatequard(x, y, val, t->rdown, nlx, my + 1, mx, nry);
else updatequard(x, y, val, t->rup, mx + 1, my + 1, nrx, nry);
t->val = gcd2(
gcd2(get_(t->ldown), get_(t->lup)),
gcd2(get_(t->rdown), get_(t->rup))
);
}
void update(int P, int Q, long long K) {
updatequard(P, Q, K, root, 0, 0, N, N);
}
long long get(int llx, int lly, int rrx, int rry, node *t, int nlx, int nly, int nrx, int nry) {
if (!t)return 0ll;
if (in_(llx, lly, rrx, rry, nlx, nly) && in_(llx, lly, rrx, rry, nrx, nry))return t->val;
int mx = (nlx + nrx) / 2;
int my = (nly + nry) / 2;
long long cur = 0;
if (in_rect(llx, lly, rrx, rry, nlx, nly, mx, my))cur = gcd2(cur, get(llx, lly, rrx, rry, t->ldown, nlx, nly, mx, my));
if (in_rect(llx, lly, rrx, rry, mx + 1, nly, nrx, my))cur = gcd2(cur, get(llx, lly, rrx, rry, t->lup, mx + 1, nly, nrx, my));
if (in_rect(llx, lly, rrx, rry, nlx, my + 1, mx, nry))cur = gcd2(cur, get(llx, lly, rrx, rry, t->rdown, nlx, my + 1, mx, nry));
if (in_rect(llx, lly, rrx, rry, mx + 1, my + 1, nrx, nry))cur = gcd2(cur, get(llx, lly, rrx, rry, t->rup, mx + 1, my + 1, nrx, nry));
return cur;
}
long long calculate(int P, int Q, int U, int V) {
return get(P, Q, U, V, root, 0, 0, N, N);
}
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;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
