| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 32056 |
2017-09-23T17:34:08 Z |
imeimi2000 |
Game (IOI13_game) |
C++14 |
|
0 ms |
952 KB |
#include "game.h"
using namespace std;
typedef long long llong;
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 nodeY {
nodeY *l, *r;
llong sum;
} treeY[30 * 30 * 30000];
struct nodeX {
nodeX *l, *r;
nodeY *t;
} treeX[30 * 30000];
nodeX * root;
nodeY * makeY() {
static int top = 0;
return treeY + (top++);
}
nodeX * makeX() {
static int top = 0;
treeX[top].t = makeY();
return treeX + (top++);
}
int n, m;
void init(int r, int c) {
n = r; m = c;
root = makeX();
root->l = root->r = root;
root->t->l = root->t->r = root->t;
}
int p, q, u, v, k, uk;
void updtY(nodeY * now, nodeY * pre, int x, int y) {
if (x == y) {
now->sum = uk;
return;
}
int md = (x + y) / 2;
if (q <= md) {
now->l = makeY();
now->r = pre->r;
updtY(now->l, pre->l, x, md);
}
else {
now->l = pre->l;
now->r = makeY();
updtY(now->r, pre->r, md + 1, y);
}
now->sum = gcd2(now->l->sum, now->r->sum);
}
llong queryY(nodeY * now, int x, int y) {
if (v < x || y < q) return 0ll;
if (q <= x && y <= v) return now->sum;
int md = (x + y) / 2;
return gcd2(queryY(now->l, x, md), queryY(now->r, md + 1, y));
}
void updtX(nodeX * now, nodeX * pre, int x, int y) {
if (x == y) {
uk = k;
updtY(now->t, pre->t, 0, m - 1);
return;
}
int md = (x + y) / 2;
if (p <= md) {
now->l = makeX();
now->r = pre->r;
updtX(now->l, pre->l, x, md);
}
else {
now->l = pre->l;
now->r = makeX();
updtX(now->r, pre->r, md + 1, y);
}
uk = gcd2(queryY(now->l->t, 0, m - 1), queryY(now->r->t, 0, m - 1));
updtY(now->t, pre->t, 0, m - 1);
}
llong queryX(nodeX * now, int x, int y) {
if (u < x || y < p) return 0ll;
if (p <= x && y <= u) return queryY(now->t, 0, m - 1);
int md = (x + y) / 2;
return gcd2(queryX(now->l, x, md), queryX(now->r, md + 1, y));
}
void update(int P, int Q, llong K) {
p = u = P;
q = v = Q;
k = K;
nodeX * pre = root;
root = makeX();
updtX(root, pre, 0, n - 1);
}
long long calculate(int P, int Q, int U, int V) {
p = P; q = Q; u = U; v = V;
return queryX(root, 0, n - 1);
}
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 |
952 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 |
952 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 |
952 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 |
952 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 |
952 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
