| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 332905 | gmyu | 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.
/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define fst first
#define snd second
#define pb push_back
#define trav(u, adj_v) for (auto& u: adj_v)
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 100007
#define MAXE 100007
const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
int x, y;
int val;
int visited;
bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
int from, to;
ll weight;
bool operator<(EDGE other) const { return weight < other.weight; }
};
/// code from USACO examples
void setIO(string name) {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
bool debug = false, submit = true;
long long gcd2(long long X, long long Y) {
if(X == 0) return Y;
if(Y == 0) return X;
long long tmp;
while (X != Y && Y != 0) {
tmp = X; X = Y;
Y = tmp % Y;
}
return X;
}
/// 2D segment tree
struct NODEX {
int lp, rp; // left ptr, right ptr
int treeV;
};
vector<NODEX> nx;
int NXseg[2];
struct NODEY {
int lp, rp; // left ptr, right ptr
ll g;
};
vector<NODEY> ny;
int NYseg[2];
int newNX(){ nx.pb((NODEX) {-1, -1, -1}); return nx.size() - 1; }
int newNY(){ ny.pb((NODEY) {-1, -1, 0}); return ny.size() - 1; }
int nn;
void pullY(int v) {
ll g1 = (ny[v].lp == -1) ? 0 : ny[ny[v].lp].g;
ll g2 = (ny[v].rp == -1) ? 0 : ny[ny[v].rp].g;
ny[v].g = gcd2(g1, g2);
if(debug) cout << " .. pull Y " << ny[v].g << endl;
}
void updY(int vty, ll val, int v, int l = NYseg[0], int r = NYseg[1]){
if(debug) cout << " .. go to Y (" << l << "," << r << ")" << endl;
if(l == r) { // leaf
ny[v].g = val;
if(debug) cout << " .. assign Y " << ny[v].g << endl;
return;
}
int mid = (l + r) / 2;
if (vty <= mid) {
if(ny[v].lp == -1) { nn = newNY(); ny[v].lp = nn; };
updY(vty, val, ny[v].lp, l, mid);
} else {
if(ny[v].rp == -1) { nn = newNY(); ny[v].rp = nn; };
updY(vty, val, ny[v].rp, mid+1, r);
}
pullY(v);
}
ll queY(int qle, int qri, int v, int l = NYseg[0], int r = NYseg[1]) {
if(r < qle || l > qri) return 0LL;
if(qle <= l && r <= qri) return ny[v].g;
int mid = (l + r) / 2;
ll g1 = (ny[v].lp == -1) ? 0LL : queY(qle, qri, ny[v].lp, l, mid);
ll g2 = (ny[v].rp == -1) ? 0LL : queY(qle, qri, ny[v].rp, mid+1, r);
return gcd2(g1, g2);
}
void pullX(int vty, int v) {
ll g1 = (nx[v].lp == -1) ? 0LL : queY(vty, vty, nx[nx[v].lp].treeV);
ll g2 = (nx[v].rp == -1) ? 0LL : queY(vty, vty, nx[nx[v].rp].treeV);
ll g0 = gcd2(g1, g2);
if(debug) cout << " pull up X, update Y seg at X=" << v << " of val=" << g1 << " " << g2 << " " << g0 << " for Y tree " << nx[v].treeV <<endl;
updY(vty, g0, nx[v].treeV);
}
void updX(int vtx, int vty, ll val, int v = 0, int l = NXseg[0], int r = NXseg[1]){
if(debug) cout << " come to X=" << v << " at (" << l << "," << r << ") with Y tree " << nx[v].treeV << endl;
if(nx[v].treeV == -1) { nn = newNY(); nx[v].treeV = nn; }
if(debug) cout << " come to X=" << v << " at (" << l << "," << r << ") with Y tree " << nx[v].treeV << endl;
if(l == r) { // leaf
if(debug) cout << " at X leaf, update Y seg at X=" << v << " at (" << l << "," << r << ")" << " for Y tree " << nx[v].treeV << endl;
updY(vty, val, nx[v].treeV);
return;
}
int mid = (l + r) / 2;
if (vtx <= mid) {
if(nx[v].lp == -1) { nn = newNX(); nx[v].lp = nn; }
updX(vtx, vty, val, nx[v].lp, l, mid);
} else {
if(nx[v].rp == -1) { nn = newNX(); nx[v].rp = nn; }
updX(vtx, vty, val, nx[v].rp, mid+1, r);
}
pullX(vty, v);
}
ll queX(int qxle, int qxri, int qyle, int qyri, int v = 0, int l = NXseg[0], int r = NXseg[1]) {
if(r < qxle || l > qxri) return 0LL;
if(qxle <= l && r <= qxri) {
if(debug) cout << " at X leaf, que Y seg at X=" << v << " at (" << l << "," << r << ")" << endl;
return (nx[v].treeV == -1) ? 0 : queY(qyle, qyri, nx[v].treeV);
}
int mid = (l + r) / 2;
ll g1 = (nx[v].lp == -1) ? 0LL : queX(qxle, qxri, qyle, qyri, nx[v].lp, l, mid);
ll g2 = (nx[v].rp == -1) ? 0LL : queX(qxle, qxri, qyle, qyri, nx[v].rp, mid+1, r);
if(debug) cout << " que X=(" << l << "," << r << ") = " << gcd2(g1, g2) << endl;
return gcd2(g1, g2);
}
void init(int R, int C) {
NXseg[0] = 0; NXseg[1] = C - 1;
NYseg[0] = 0; NYseg[1] = R - 1;
newNX();
}
void update(int P, int Q, long long K) {
updX(Q, P, K);
}
long long calculate(int y10, int x10, int y20, int x20) {
int x1 = min(x10, x20), x2 = max(x10, x20);
int y1 = min(y10, y20), y2 = max(y10, y20);
return queX(x1, x2, y1, y2);
}