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 "game.h"
/**
* Author: Nicholas Winschel
* Created: 05.23.2023 20:57:47
**/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())
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;
}
const int inf = 1e9+20;
struct lt {
lt *l=NULL, *r=NULL;
int p;
pi x;
ll c,g;
lt () : p (rand()), x(-1,-1), c(0),g(0) {}
void upd() {
g = gcd(c,gcd(l ? l->g : 0, r ? r->g : 0));
}
friend void split(lt *t, lt *&wl, lt *&wr, const pi &X) {
if (!t) {
wl=wr=NULL;
return;
}
if (t->x <= X) {
split(t->r,t->r,wr,X);
wl=t;
} else {
split(t->l,wl,t->l,X);
wr=t;
}
t->upd();
}
friend void merge(lt *tl, lt *tr, lt *&i) {
// cerr << "test4" << " " << tl << " " << tr << endl;
assert(tl != tr);
if (!tl || !tr) {
i = (tl ? tl : tr);
return;
}
if (tl->p < tr->p) {
merge(tl,tr->l,tr->l);
i=tr;
} else {
merge(tl->r,tr,tl->r);
i=tl;
}
i->upd();
}
static void op(lt *&root, const pi &X, ll val) {
// cerr << "test" << endl;
lt *lp=NULL,*rp=NULL;
split(root,root,rp,X);
split(root,lp,root,{X.f,X.s-1});
if (!root) {
root = new lt;
root->x=X;
}
root->g=root->c=val;
// cerr << "test3" << endl;
merge(lp,root,root);
merge(root,rp,root);
}
static ll q(lt *&root, int xl, int xr) {
lt *lp=NULL,*rp=NULL;
split(root,root,rp,{xr, inf});
split(root,lp,root,{xl,-inf});
ll ret=0; if (root) ret=root->g;
merge(lp,root,root);
merge(root,rp,root);
return ret;
}
};
struct sstot {
sstot *l=NULL, *r=NULL;
int s,e;
lt *t;
sstot () {
t=new lt;
}
void op(const pi &X, ll val) {
// cerr << "test2 " << X.f << " " << X.s << " " << val << endl;
lt::op(t,X,val);
if (e-s <= 1) return;
int y = X.s;
int m = (s+e)>>1;
if (y < m) {
if (!l) l = new sstot;
l->s=s;
l->e=m;
l->op(X,val);
} else {
if (!r) r = new sstot;
r->s=m;
r->e=e;
r->op(X,val);
}
}
ll q(int xl, int xr, int yl, int yr) {
if (yl >= e || yr < s) return 0;
if (yl <= s && yr >= e-1) return lt::q(t,xl,xr);
int m = (s+e)>>1;
return gcd((l ? l->q(xl,xr,yl,yr) : 0), (r ? r->q(xl,xr,yl,yr) : 0));
}
// ll q(int xl, int xr, int yl, int yr) {
// ll ans = _q(xl,xr,yl,yr);
// cerr << "dbg: y=[" << s << "," << e << "): " << "\n q=[" << xl << "," << xr << "]*["
// << yl << "," << yr << "]\n ans=" << ans << "\n";
// return ans;
// }
};
sstot root;
void init(int R, int C) {
root=sstot();
root.s=0;
root.e=inf;
}
void update(int P, int Q, long long K) {
root.op({Q,P},K);
}
long long calculate(int P, int Q, int U, int V) {
return root.q(min(Q,V),max(Q,V),min(P,U),max(P,U));
}
Compilation message (stderr)
game.cpp: In member function 'll sstot::q(int, int, int, int)':
game.cpp:124:13: warning: unused variable 'm' [-Wunused-variable]
124 | int m = (s+e)>>1;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |