| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 417970 |
2021-06-04T17:25:17 Z |
Mlxa |
Game (IOI13_game) |
C++14 |
|
1825 ms |
17956 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "game.h"
ll gcd(ll x, ll y) {
ll tmp;
while (x != y && y != 0) {
tmp = x;
x = y;
y = tmp % y;
}
return x;
}
const int TREAP_NODES = 1e6;
mt19937 rnd;
namespace dd {
struct treap {
int ls, rs, ke, pr;
ll va, gc;
} pool[TREAP_NODES];
int treap_ff = 1;
#define gt(x,type) type &x(int v) { assert(0 <= v && v < TREAP_NODES); return pool[v].x; }
gt(ls,int) gt(rs,int) gt(ke,int) gt(pr,int) gt(va,ll) gt(gc,ll)
#undef gt
int new_node(int x, ll q) {
int v = treap_ff++;
ls(v) = rs(v) = 0;
ke(v) = x;
pr(v) = (int)rnd();
va(v) = gc(v) = q;
return v;
}
int pull(int v) {
gc(v) = gcd(va(v), gcd(gc(ls(v)), gc(rs(v))));
return v;
}
int merge(int l, int r) {
if (!l) {
return r;
}
if (!r) {
return l;
}
if (pr(l) < pr(r)) {
rs(l) = merge(rs(l), r);
return pull(l);
} else {
ls(r) = merge(l, ls(r));
return pull(r);
}
}
pair<int, int> split(int t, int x) {
if (!t) {
return {t, t};
}
int l, r;
if (x < ke(t)) {
tie(l, ls(t)) = split(ls(t), x);
r = pull(t);
} else {
tie(rs(t), r) = split(rs(t), x);
l = pull(t);
}
return {l, r};
}
ll query(int t, int ql, int qr) {
int tl, tm, tr;
tie(tl, tm) = split(t, ql - 1);
tie(tm, tr) = split(tm, qr - 1);
ll res = gc(tm);
int nt = merge(merge(tl, tm), tr);
assert(t == nt);
return res;
}
__attribute__((warn_unused_result))
int upd(int t, int pos, ll val) {
int tl, tm, tr;
tie(tl, tm) = split(t, pos - 1);
tie(tm, tr) = split(tm, pos);
if (tm) {
assert(!ls(tm) && !rs(tm));
assert(ke(tm) == pos);
va(tm) = gc(tm) = val;
} else {
tm = new_node(pos, val);
}
return merge(merge(tl, tm), tr);
}
void print(int t, int h = 0) {
if (t) {
print(ls(t), h + 1);
cout << ke(t) << ":" << va(t) << " ";
print(rs(t), h + 1);
}
if (!h) {
cout << endl;
}
}
}
const int ST_NODES = 1e6;
const int RANGE = 1e9 + 10;
struct node {
int ls, rs, tr;
} pool[ST_NODES];
int ff_st = 1;
#define gt(x,type) type &x(int v) { assert(0 <= v && v < ST_NODES); return pool[v].x; }
gt(ls,int) gt(rs,int) gt(tr,int)
#undef gt
int new_node() {
int v = ff_st++;
ls(v) = rs(v) = tr(v) = 0;
return v;
}
ll query(int v, int vl, int vr, int ql, int qr, int yl, int yr) {
if (!v || qr <= vl || vr <= ql) {
return 0;
}
if (ql <= vl && vr <= qr) {
return dd::query(tr(v), yl, yr);
}
int vm = (vl + vr) / 2;
return gcd(query(ls(v), vl, vm, ql, qr, yl, yr), query(rs(v), vm, vr, ql, qr, yl, yr));
}
__attribute__((warn_unused_result))
int upd(int v, int vl, int vr, int x, int y, ll to) {
assert(vl <= x && x < vr);
if (!v) {
v = new_node();
}
if (vr - vl == 1) {
tr(v) = dd::upd(tr(v), y, to);
return v;
}
int vm = (vl + vr) / 2;
if (x < vm) {
ls(v) = upd(ls(v), vl, vm, x, y, to);
ll nval = dd::query(tr(rs(v)), y, y + 1);
nval = gcd(nval, to);
tr(v) = dd::upd(tr(v), y, nval);
} else {
rs(v) = upd(rs(v), vm, vr, x, y, to);
ll nval = dd::query(tr(ls(v)), y, y + 1);
nval = gcd(nval, to);
tr(v) = dd::upd(tr(v), y, nval);
}
return v;
}
void init(int r, int c) {
(void)r; (void)c;
}
int root = 0;
void dfs(int v, int vl, int vr) {
if (!v) {
return;
}
cout << "#\t" << vl << " " << vr << endl;
dd::print(tr(v));
int vm = (vl + vr) / 2;
dfs(ls(v), vl, vm);
dfs(rs(v), vm, vr);
}
void update(int p, int q, ll k) {
root = upd(root, 0, RANGE, p, q, k);
}
ll calculate(int p, int q, int u, int v) {
return query(root, 0, RANGE, p, u + 1, q, v + 1);
}
#ifdef LC
#include "grader.c"
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1825 ms |
17956 KB |
Output is correct |
| 5 |
Incorrect |
1055 ms |
17692 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
