| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 573197 | Theo830 | Game (IOI13_game) | C++17 | 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>
using namespace std;
typedef int ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define ull unsigned ll
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
//#include "game.h"
vector<ii>py,px;
long long seg[50000][50000];
ll cx = 1,cy = 1;
ll N,M;
ll em = 32 * 10000 + 5;
void init(int R, int C){
py.assign(em,ii(-1,-1));
px.assign(em,ii(-1,-1));
N = R;
M = C;
}
void upd_y(ll lx,ll rx,ll curx,ll ly,ll ry,ll cury,ll X,ll Y,long long val){
if(ly == ry){
if(lx == rx){
seg[curx][cury] = val;
}
else{
seg[curx][cury] = 0;
if(px[curx].F != -1){
seg[curx][cury] = __gcd(seg[curx][cury],seg[px[curx].F][cury]);
}
if(px[curx].S != -1){
seg[curx][cury] = __gcd(seg[curx][cury],seg[px[curx].S][cury]);
}
}
}
else{
ll mid = (ly+ry)/2;
if(Y <= mid){
if(py[cury].F == -1){
py[cury].F = cy;
cy++;
}
upd_y(lx,rx,curx,ly,mid,py[cury].F,X,Y,val);
}
else{
if(py[cury].S == -1){
py[cury].S = cy;
cy++;
}
upd_y(lx,rx,curx,mid+1,ry,py[cury].S,X,Y,val);
}
seg[curx][cury] = 0;
if(py[cury].F != -1){
ll pos = py[cury].F;
seg[curx][cury] = __gcd(seg[curx][cury],seg[curx][pos]);
}
if(py[cury].S != -1){
ll pos = py[cury].S;
seg[curx][cury] = __gcd(seg[curx][cury],seg[curx][pos]);
}
}
}
void upd_x(ll lx,ll rx,ll curx,ll X,ll Y,long long val){
if(lx != rx){
ll mid = (lx + rx) / 2;
if(X <= mid){
if(px[curx].F == -1){
px[curx].F = cx;
cx++;
}
upd_x(lx,mid,px[curx].F,X,Y,val);
}
else{
if(px[curx].S == -1){
px[curx].S = cx;
cx++;
}
upd_x(mid+1,rx,px[curx].S,X,Y,val);
}
}
upd_y(lx,rx,curx,0,M-1,0,X,Y,val);
}
ll ask_y(ll lx,ll rx,ll curx,ll ly,ll ry,ll cury,ll X1,ll X2,ll Y1,ll Y2){
if(Y1 <= ly && ry <= Y2){
return seg[curx][cury];
}
if(ly > Y2 || Y1 > ry){
return 0;
}
ll ans = 0;
ll mid = (ly + ry) / 2;
if(py[cury].F != -1){
ans = __gcd(ans,ask_y(lx,rx,curx,ly,mid,py[cury].F,X1,X2,Y1,Y2));
}
if(py[cury].S != -1){
ans = __gcd(ans,ask_y(lx,rx,curx,mid+1,ry,py[cury].S,X1,X2,Y1,Y2));
}
return ans;
}
ll ask_x(ll lx,ll rx,ll curx,ll X1,ll X2,ll Y1,ll Y2){
if(X1 <= lx && rx <= X2){
return ask_y(lx,rx,curx,0,M-1,0,X1,X2,Y1,Y2);
}
if(lx > X2 || X1 > rx){
return 0;
}
ll ans = 0;
ll mid = (lx + rx) / 2;
if(px[curx].F != -1){
ans = __gcd(ans,ask_x(lx,mid,px[curx].F,X1,X2,Y1,Y2));
}
if(px[curx].S != -1){
ans = __gcd(ans,ask_x(mid+1,rx,px[curx].S,X1,X2,Y1,Y2));
}
return ans;
}
void update(int P, int Q, long long K) {
upd_x(0,N-1,0,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return ask_x(0,N-1,0,P,U,Q,V);
}
/*
#define MAX_SIZE 1000000000
#define MAX_N 272000
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int R, C, N;
int P, Q, U, V;
long long K;
int i, type;
int res;
res = scanf("%d", &R);
res = scanf("%d", &C);
res = scanf("%d", &N);
init(R, C);
for (i = 0; i < N; i++) {
res = scanf("%d", &type);
if (type == 1) {
res = scanf("%d%d%lld", &P, &Q, &K);
update(P, Q, K);
} else if (type == 2) {
res = scanf("%d%d%d%d", &P, &Q, &U, &V);
cout<<calculate(P, Q, U, V)<<"\n";
}
}
return 0;
}
2 3 9
1 0 0 20
1 0 2 15
1 1 1 12
2 0 0 0 2
2 0 0 1 1
1 0 1 6
1 1 1 14
2 0 0 0 2
2 0 0 1 1
*/