| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 122031 | yusufake | Game (IOI13_game) | C++98 | 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;
#define _ int v, int tl, int tr
#define tm (tl + tr >> 1)
typedef long long ll;
typedef pair < int , int > pp;
const int mod = 1e9 + 7;
const int x_N = 22000 * 30;
const int y_N = 22000 * 30 * 30;
int x_to_Y[x_N],x_L[x_N],x_R[x_N],x_id = 1;
int y_L[y_N],y_R[y_N],y_id;
ll s[y_N]; // segment tree values are stored only for -y axis
// 0 is empty node
// s[0] should be ineffective element
// x_to_Y[0], L[0], and R[0] should be 0
// 1 is the root of the -x axis segment tree
// x_to_Y[v] is the root of the segment tree of the interval that corresponds to node 'v' in -x axis segment tree
ll gcd(ll u, ll v) {
ll r;
while (v != 0) { r = u % v; u = v; v = r; }
return u;
}
ll qry_y(_, int ly, int ry) {
if(ly > tr || ry < tl || !v) return 0;
if (ly <= tl && tr <= ry) return s[v];
return gcd(qry_y(y_L[v],tl,tm,ly,ry) , qry_y(y_R[v],tm+1,tr,ly,ry));
}
ll qry_x(_, int lx, int rx, int ly, int ry) {
if(lx > tr || rx < tl) return 0;
if (lx <= tl && tr <= rx) return qry_y(x_to_Y[v], 0, mod, ly, ry);
return gcd(qry_x(x_L[v],tl,tm,lx,rx,ly,ry) , qry_x(x_R[v],tm+1,tr,lx,rx,ly,ry));
}
void up_y(_, int posy, int r1, int r2, ll t){
if(tl == tr){
s[v] = t == -1 ? gcd(s[r1] , s[r2]) : t;
return;
}
if(posy > tm) { if(!y_R[v]) y_R[v] = ++y_id; up_y(y_R[v],tm+1,tr,posy,y_R[r1],y_R[r2],t); }
else { if(!y_L[v]) y_L[v] = ++y_id; up_y(y_L[v],tl,tm, posy,y_L[r1],y_L[r2],t); }
s[v] = gcd(s[ y_L[v] ] , s[ y_R[v] ]);
}
void up_x(_, int posx, int posy, ll t){
if(tl < tr){
if(posx > tm) { if(!x_R[v]) x_R[v] = ++x_id; up_x(x_R[v],tm+1,tr,posx,posy,t); }
else { if(!x_L[v]) x_L[v] = ++x_id; up_x(x_L[v],tl,tm, posx,posy,t); }
}
if(!x_to_Y[v]) x_to_Y[v] = ++y_id;
up_y(x_to_Y[v],0,mod,posy,x_to_Y[ x_L[v] ],x_to_Y[ x_R[v] ],(tl==tr?t:-1));
}
void update(int posx, int posy, ll t){
up_x(1,0,mod,posx,posy,t);
}
ll calculate(int lx, int ly, int rx, int ry){
return qry_x(1,0,mod,lx,rx,ly,ry);
}
void init(int a, int b) {
memset(s , 0 , sizeof s);
memset(x_L , 0 , sizeof x_L);
memset(x_R , 0 , sizeof x_R);
memset(y_L , 0 , sizeof y_L);
memset(y_R , 0 , sizeof y_R);
memset(x_to_Y , 0 , sizeof x_to_Y)
}