| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 157035 |
2019-10-09T08:20:45 Z |
topology |
Game (IOI13_game) |
C++17 |
|
296 ms |
256004 KB |
#include <bits/stdc++.h>
#ifdef TOPOLOGY
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#include "game.h"
#define debug(...)
#endif
using namespace std;
int rr, cc;
long long gcd2(long long X, long long Y);
struct node {
long long g;
int q, v;
node *l, *r;
node(int q_, int v_) : g(), q(q_), v(v_), l(), r() {
}
long long upd(int q, long long k) {
if (q < this->q || this->v < q) return this->g;
if (this->q == this->v) {
return this->g = k;
}
int m = (this->q + this->v) >> 1;
node *&nd = q <= m ? this->l : this->r;
if (!nd) nd = new node(q, q);
else if (q < nd->q || nd->v < q) {
int n_q = this->q, n_v = this->v;
node *old_nd = nd;
while (true) {
// debug("%d %d\n", n_q, n_v);
int n_m = (n_q + n_v) >> 1;
if (n_m >= max(q, nd->v)) n_v = n_m;
else if (n_m < min(q, nd->q)) n_q = n_m + 1;
else {
nd = new node(n_q, n_v);
if (q < nd->q) nd->r = old_nd;
else nd->l = old_nd;
break;
}
}
}
return this->g = gcd2(
this->l ? this->l->upd(q, k) : 0,
this->r ? this->r->upd(q, k) : 0
);
}
long long gcd(int qi, int vi, int q, int v) {
if (vi < q || qi > v) return 0LL;
if (q <= qi && vi <= v) {
return this->g;
}
return gcd2(
this->l ? this->l->gcd(qi, (qi + vi) >> 1, q, v) : 0LL,
this->r ? this->r->gcd(((qi + vi) >> 1) + 1, vi, q, v) : 0LL
);
}
};
struct hnode {
node *seg;
hnode *l, *r;
hnode() : l(), r() {
this->seg = new node(0, cc - 1);
}
long long upd(int pi, int ui, int p, int q, long long k) {
if (p < pi || ui < p) {
return this->seg->gcd(0, cc - 1, q, q);
} else if (pi < ui) {
if (p <= ((pi + ui) >> 1) && !this->l) this->l = new hnode();
if (p > ((pi + ui) >> 1) && !this->r) this->r = new hnode();
long long l = gcd2(
this->l ? this->l->upd(pi, (pi + ui) >> 1, p, q, k) : 0,
this->r ? this->r->upd(((pi + ui) >> 1) + 1, ui, p, q, k) : 0
);
this->seg->upd(q, l);
return l;
} else {
this->seg->upd(q, k);
return k;
}
}
long long gcd(int pi, int ui, int p, int q, int u, int v) {
if (ui < p || pi > u) return 0LL;
if (p <= pi && ui <= u) {
return this->seg->gcd(0, cc - 1, q, v);
}
return gcd2(
this->l ? this->l->gcd(pi, (pi + ui) >> 1, p, q, u, v) : 0LL,
this->r ? this->r->gcd(((pi + ui) >> 1) + 1, ui, p, q, u, v) : 0LL
);
}
} *root;
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;
}
void init(int r, int c) {
rr = r;
cc = c;
root = new hnode();
}
void update(int p, int q, long long k) {
root->upd(0, rr - 1, p, q, k);
}
long long calculate(int p, int q, int u, int v) {
/* ... */
return root->gcd(0, rr - 1, p, q, u, v);
}
#ifdef TOPOLOGY
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int R, C, N;
cin >> R >> C >> N;
init(R, C);
cout << "init(" << R << ", " << C << ")\n";
for (int i = 0; i < N; i++) {
int D;
cin >> D;
if (D == 1) {
int P, Q;
long long K;
cin >> P >> Q >> K;
update(P, Q, K);
cout << "update(" << P << ", " << Q << ", " << K << ")\n";
} else {
int P, Q, U, V;
cin >> P >> Q >> U >> V;
long long res = calculate(P, Q, U, V);
cout << "calculate(" << P << ", " << Q << ", " << U << ", " << V << ") " << res << '\n';
}
}
return 0;
}
#endif
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 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
296 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 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 |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
252 KB |
Output is correct |
| 2 |
Runtime error |
273 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Runtime error |
278 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Runtime error |
279 ms |
256000 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
