| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 42760 | 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>
using namespace std;
#define _ int v, int tl, int tr
#define tm (tl+tr >> 1)
#define sol L[v],tl,tm
#define sag R[v],tm+1,tr
#define mp make_pair
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef pair < int , int > pp;
const int mod = 1e9 + 7;
const int N = 1e4 + 4;
int Y[N*8],L[N*200],R[N*200],posx,posy,lx,ly,rx,ry,id;
ll s[N*200],tt;
ll qry_y(_) {
if(ly > tr || ry < tl || !v) return 0;
if (ly <= tl && tr <= ry) return s[v];
return __gcd(qry_y(sol) , qry_y(sag));
}
ll qry_x(_) {
if(lx > tr || rx < tl) return 0;
if (lx <= tl && tr <= rx) return qry_y(Y[v], 0, mod);
return __gcd(qry_x(v+v,tl,tm) , qry_x(v+v+1,tm+1,tr));
}
void up_y(_, int r1, int r2, bool h){ // s[0] should contain ineffective element
if(tl == tr){
if(tl != posy) return;
if(h) s[v] = tt;
else s[v] = __gcd(s[r1] , s[r2]);
return;
}
if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,R[r1],R[r2],h); }
else { if(!L[v]) L[v] = ++id; up_y(sol,L[r1],L[r2],h); }
s[v] = __gcd(s[ L[v] ] , s[ R[v] ]);
}
void up_x(_){
if(tl < tr){
if(posx > tm) up_x(v+v+1,tm+1,tr);
else up_x(v+v,tl,tm);
}
if(!Y[v]) Y[v] = ++id;
up_y(Y[v],0,mod,Y[v+v],Y[v+v+1],(tl==tr));
}
void update(int x, int y, ll t){
posx = x;
posy = y;
tt = t;
up_x(1,0,mod);
}
ll calculate(int a, int b, int a2, int b2){
lx = a; ly = b;
rx = a2; ry = b2;
return qry_x(1,0,mod);
}
void init(int a, int b) {}