| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 390305 |
2021-04-15T19:48:11 Z |
rainboy |
Game (IOI13_game) |
C |
|
1 ms |
332 KB |
#include "game.h"
#define LG 30 /* LG = ceil(log2(10^9)) */
#define NU 22000
#define N (NU * (LG + 1))
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
int zz[1 + N], ll[1 + N], rr[1 + N], jj[1 + N], u_, l_, r_; long long xx[1 + N], yy[1 + N];
int node(int j) {
static int _ = 1;
zz[_] = rand_();
jj[_] = j;
return _++;
}
void pul(int u) {
yy[u] = gcd(xx[u], gcd(yy[ll[u]], yy[rr[u]]));
}
void split(int u, int j) {
if (u == 0) {
u_ = l_ = r_ = 0;
return;
}
if (jj[u] < j) {
split(rr[u], j);
rr[u] = l_, l_ = u;
} else if (jj[u] > j) {
split(ll[u], j);
ll[u] = r_, r_ = u;
} else {
u_ = u, l_ = ll[u], r_ = rr[u];
ll[u] = rr[u] = 0;
}
pul(u);
}
int merge(int u, int v) {
if (u == 0)
return v;
if (v == 0)
return u;
if (zz[u] < zz[v]) {
rr[u] = merge(rr[u], v), pul(u);
return u;
} else {
ll[v] = merge(u, ll[v]), pul(v);
return v;
}
}
int uu[1 + N], ll_[1 + N], rr_[1 + N], t_, __ = 1, r, c;
void init(int R, int C) {
r = R, c = C;
}
int update2(int u, int j, long long x) {
split(u, j);
if (u_ == 0)
u_ = node(j);
xx[u_] = yy[u_] = x;
return merge(merge(l_, u_), r_);
}
int update1(int t, int il, int ir, int i, int j, long long x) {
if (t == 0)
t = __++;
uu[t] = update2(uu[t], j, x);
if (ir - il > 1) {
int im = (il + ir) / 2;
if (i < im)
ll_[t] = update1(ll_[t], il, im, i, j, x);
else
rr_[t] = update1(rr_[t], im, ir, i, j, x);
}
return t;
}
long long ans;
void query2(int u, int j1, int j2, int type) {
if (u == 0)
return;
if (type == 0) {
if (j2 <= jj[u])
query2(ll[u], j1, j2, 0);
else if (j1 > jj[u])
query2(rr[u], j1, j2, 0);
else {
ans = gcd(ans, xx[u]);
query2(ll[u], j1, j2, 1), query2(rr[u], j1, j2, -1);
}
} else if (type == -1) {
if (j2 <= jj[u])
query2(ll[u], j1, j2, -1);
else {
ans = gcd(gcd(ans, yy[ll[u]]), xx[u]);
query2(rr[u], j1, j2, -1);
}
} else if (type == 1) {
if (j1 > jj[u])
query2(rr[u], j1, j2, 1);
else {
ans = gcd(gcd(ans, yy[rr[u]]), xx[u]);
query2(ll[u], j1, j2, 1);
}
}
}
void query1(int t, int il, int ir, int i1, int i2, int j1, int j2) {
int im;
if (i2 <= il || ir <= i1 || uu[t] == 0)
return;
if (i1 <= il && ir <= i2) {
query2(uu[t], j1, j2, 0);
return;
}
im = (il + ir) / 2;
query1(ll_[t], il, im, i1, i2, j1, j2);
query1(rr_[t], im, ir, i1, i2, j1, j2);
}
void update(int i, int j, long long x) {
t_ = update1(t_, 0, r, i, j, x);
}
long long calculate(int i1, int j1, int i2, int j2) {
i2++, j2++;
ans = 0, query1(t_, 0, r, i1, i2, j1, j2);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
