| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 156549 |
2019-10-06T12:47:53 Z |
topology |
Game (IOI13_game) |
C++17 |
|
6 ms |
1144 KB |
#include <bits/stdc++.h>
#ifdef TOPOLOGY
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#include "game.h"
#define debug(...)
#endif
using namespace std;
long long gcd2(long long X, long long Y);
struct node {
int q;
int v;
unordered_map<int, long long> ns;
long long g;
node *l, *r;
node(int q_, int v_) : q(q_), v(v_), ns(), g(), l(), r() {
}
void upd(int q, long long k) {
if (q < this->q || this->v < q) return;
ns.erase(q);
if (k) ns.emplace(q, k);
this->g = 0LL;
for (auto &p : ns) {
this->g = gcd2(this->g, p.second);
}
if (this->q < this->v) {
if (!this->l) this->l = new node(this->q, (this->q + this->v) >> 1);
if (!this->r) this->r = new node(((this->q + this->v) >> 1) + 1, this->v);
this->l->upd(q, k);
this->r->upd(q, k);
}
}
long long gcd(int q, int v) {
if (this->v < q || this->q > v) return 0LL;
if (q <= this->q && this->v <= v) {
return this->g;
}
return gcd2(
this->l ? this->l->gcd(q, v) : 0,
this->r ? this->r->gcd(q, v) : 0
);
}
};
struct hnode {
int p;
int u;
int c;
node *seg;
hnode *l, *r;
hnode(int p_, int u_, int c_) : p(p_), u(u_), c(c_), l(), r() {
this->seg = new node(0, c - 1);
}
void upd(int p, int q, long long k) {
if (p < this->p || this->u < p) return;
this->seg->upd(q, k);
if (this->p < this->u) {
if (!this->l) this->l = new hnode(this->p, (this->p + this->u) >> 1, this->c);
if (!this->r) this->r = new hnode(((this->p + this->u) >> 1) + 1, this->u, this->c);
this->l->upd(p, q, k);
this->r->upd(p, q, k);
}
}
long long gcd(int p, int q, int u, int v) {
if (this->u < p || this->p > u) return 0LL;
if (p <= this->p && this->u <= u) {
return this->seg->gcd(q, v);
}
return gcd2(
this->l ? this->l->gcd(p, q, u, v) : 0,
this->r ? this->r->gcd(p, q, u, v) : 0
);
}
} *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) {
root = new hnode(0, r - 1, c);
}
void update(int p, int q, long long k) {
root->upd(p, q, k);
}
long long calculate(int p, int q, int u, int v) {
/* ... */
return root->gcd(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 |
Incorrect |
6 ms |
1144 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 |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
1144 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 |
5 ms |
1144 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 |
5 ms |
1144 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
