| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 620461 | MadokaMagicaFan | Game (IOI13_game) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
#include <game.h>
using namespace std;
using ll = long long;
const ll inf = 1e9;
#define sz(v) ((int)v.size())
#define pb push_back
#define fst first
#define scn second
/* #define ONPC */
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int a, int b) { return a + rng()%(b-a+1); }
/* ll gcd2(ll x, ll y); */
struct treap{
ll x, v;
int s;
int w;
int k;
treap *l, *r;
treap(ll _x, int _k) {
w = rand(0,10000);
l = r = NULL;
x = v = _x;
k = _k;
s = 1;
}
};
using tp = treap*;
int size(tp x) { return (x == NULL ? 0 : x->s); }
int xval(tp x) { return (x == NULL ? 0 : x->v); }
void
calc(tp x)
{
if (x == NULL) return;
x->s = size(x->l) + size(x->r);
x->v = gcd2(x->x,gcd2(xval(x->l),xval(x->r)));
}
void
split(tp t, tp& l, tp & r, int k)
{
if (t == NULL)
l = r = NULL;
else if (t->k > k)
split(t->l, l, t->l, k), r = t;
else
split(t->r, t->r, r, k), l = t;
calc(t);
}
void
unite(tp& t, tp l, tp r)
{
if (l == NULL) t=r;
else if (r == NULL) t=l;
else if (l->w > r->w)
unite(l->r,l->r,r), t = l;
else
unite(r->l,l,r->l), t = r;
calc(t);
}
struct aint {
int l, r;
aint *la, *ra;
tp v;
aint(int _l, int _r)
: l(_l), r(_r)
{
v = new treap(0,0);
la = ra = NULL;
}
ll
upd(int x, int y, ll val)
{
if (x < l || x > r) return getval(y,y);
if (l == r)
return set(y,val);
if (!la) la = new aint(l, (l+r)>>1);
if (!ra) ra = new aint(((l+r)>>1)+1, r);
val = gcd2(la->upd(x,y,val), ra->upd(x,y,val));
return set(y,val);
}
ll
set(int y, ll val)
{
tp a, b, c;
split(v, a, b, y-1);
split(b, b, c, y);
assert(size(b)<2);
if (b == NULL)
b = new treap(val, y);
b->x = val;
b->v = val;
unite(v, a, b);
unite(v, v, c);
return val;
}
ll
query(int lx, int rx, int ly, int ry)
{
if (rx < l || lx > r) return 0;
if (lx <= l && r <= rx) return getval(ly,ry);
ll ret = 0;
if (la) ret = gcd2(ret, la->query(lx,rx,ly,ry));
if (ra) ret = gcd2(ret, ra->query(lx,rx,ly,ry));
return ret;
}
ll
getval(int l, int r)
{
ll ret = 0;
tp a, b, c;
split(v, a, b, l-1);
split(b, b, c, r);
ret = xval(b);
unite(v, a, b);
unite(v, v, c);
return ret;
}
};
aint* root;
void
init(int R, int C)
{
root = new aint(0,R+1);
return;
}
void
update(int p, int q, long long k)
{
root->upd(p,q,k);
return;
}
ll
calculate(int p, int q, int u, int v)
{
if (p>u) swap(u,p);
if (q>v) swap(q,v);
return root->query(p, u, q, v);
}
#ifdef ONPC
ll
gcd2(ll a, ll b)
{
if (a == 0) return b;
if (b == 0) return a;
if (a < b) swap(a,b);
return gcd2(b, a%b);
}
void
solve()
{
int r, c, q;
cin >> r >> c >> q;
init(r,c);
int t, w, x, y;
ll z;
while(q--) {
cin >> t;
if (t == 1) {
cin >> x >> y >> z;
update(x,y,z);
} else {
cin >> w >> x >> y >> z;
cout << calculate(w,x,y,z) << endl;
}
}
}
int32_t
main(int argc, char **argv)
{
if (argc >= 2) {
freopen(argv[1], "r", stdin);
} else
ios_base::sync_with_stdio(0);cin.tie(0);
int t = 1;
/* cin >> t; */
while(t--)
solve();
}
#endif