| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 24231 | Parthib_Gupta | 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 "game.h"
#include <bits/stdc++.h>
typedef long long vlong;
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;
}
long long r , c ;
vector < vector <long long > > tree;
vlong qy(vlong ndx, vlong ndy, vlong st, vlong ed,vlong y1,vlong y2)
{
if(y2 < st || y1 > ed)
return 0;
if(y2 >= ed && y1 <= st){
return tree[ndx][ndy];
}
vlong md = (st+ed)/2;
vlong v1 = qy(ndx, 2*ndy, st, md, y1, y2);
vlong v2 = qy(ndx, 2*ndy + 1, md+ 1, ed, y1, y2);
return gcd2(v1, v2);
}
vlong qx(vlong nd, vlong st, vlong ed, vlong x1, vlong y1, vlong x2, vlong y2)
{
if(ed < x1 || st > x2)
return 0;
if(x1 <= st && ed <= x2){
return qy(nd, 1, 0, c-1, y1, y2);
}
vlong md = (st+ed)/2;
vlong v1 = qx(2*nd, st, md, x1, y1, x2, y2);
vlong v2 = qx(2*nd + 1, md+1, ed, x1, y1, x2, y2);
return gcd2(v1, v2);
}
void up_y(vlong ndx, vlong lx, vlong rx, vlong nd, vlong st, vlong ed, vlong y, vlong nVal)
{
if(st == ed){
if(lx == rx){
tree[ndx][nd] = nVal;
}
else{
tree[ndx][nd] = gcd2(tree[ndx*2][nd], tree[ndx*2 + 1][nd]);
}
return;
}
vlong md = (st+ed)/2;
if(y <= md)
up_y(ndx, lx, rx, nd*2, st, md, y, nVal);
else
up_y(ndx, lx, rx, nd*2 + 1, md + 1, ed, y, nVal);
tree[ndx][nd] = gcd2(tree[ndx][nd*2], tree[ndx][nd*2 + 1]);
}
void up_x(vlong nd, vlong st, vlong ed, vlong x, vlong y, vlong nVal)
{
// cerr << "I am here\n";
if(st != ed){
vlong md = (st+ed)/2;
if(x <= md) up_x(2*nd, st, md, x, y, nVal);
else up_x(2*nd + 1, md+1, ed, x, y, nVal);
}
up_y(nd, st, ed, 1, 0, c-1, y, nVal);
}
void build_Y(vlong nx, vlong sx, vlong ex, vlong nd, vlong st, vlong ed)
{
if(st == ed){
if(sx == ex){
tree[nx][nd] = 0;
}
else{
tree[nx][nd] = gcd2(tree[nx*2][nd], tree[nx*2 + 1][nd]);
}
return;
}
vlong md = (st+ed)/2;
build_Y(nx, sx, ex, 2*nd, st, md);
build_Y(nx, sx, ex, 2*nd + 1, md+1, ed);
tree[nx][nd] = gcd2(tree[nx][2*nd], tree[nx][2*nd + 1]);
}
void build_X(vlong nd, vlong st, vlong ed)
{
if(st != ed){
vlong md = (st+ed)/2;
build_X(2*nd, st, md);
build_X(2*nd + 1, md + 1, ed);
}
build_Y(nd, st, ed, 1, 0, c-1);
}
void init(int R, int C) {
r = R;
c = C;
if(r <= 2000 && c <= 2000) {
tree.resize(5000);
for(int i=0; i<5000; i++)
tree[i].assign(5000, 0);
} else {
tree.resize(30);
for(int i=0; i<30; i++)
tree[i].assign(300000, 0);
}
build_X(1, 0, R-1);
}
void update(int P, int Q, long long K) {
up_x(1, 0, r-1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return qx(1, 0, r-1, P, Q, U, V);
}