| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 574189 | 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<ii,ll>
#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;
set<iii>rax,ray;
map<ll,bool>evx,evy;
long long seg[10000][10000];
ll cx = 1,cy = 1;
ll N,M;
ll em = 32 * 22000 + 5;
void init(int R, int C){
py.assign(em,ii(0,0));
px.assign(em,ii(0,0));
N = R;
M = C;
rax.insert(iii(ii(0,-N+1),0));
ray.insert(iii(ii(0,-M+1),0));
}
void upd_y(ll lx,ll rx,ll curx,ll ly,ll ry,ll cury,ll X,ll Y,long long val){
if(Y < ly || ry < Y){
return;
}
if(ly == ry){
if(lx == rx){
seg[curx][cury] = val;
}
else{
seg[curx][cury] = 0;
ll mid = (lx + rx) / 2;
auto it = rax.lower_bound(iii(ii(lx,-rx + 1),0));
if(it != rax.end() && -(*it).F.S <= mid){
seg[curx][cury] = __gcd(seg[curx][cury],seg[(*it).S][cury]);
}
it = rax.lower_bound(iii(ii(mid+1,-INF),0));
if(it != rax.end() && -(*it).F.S <= rx){
seg[curx][cury] = __gcd(seg[curx][cury],seg[((*it).S)][cury]);
}
}
}
else{
ll mid = (ly+ry)/2;
if(Y <= mid){
if(py[cury].S){
if(!py[cury].F){
ray.insert(iii(ii(ly,-ry),cy));
cy++;
}
}
py[cury].F = 1;
auto it = ray.lower_bound(iii(ii(ly,-ry + 1),0));
if(-(*it).F.S <= mid){
upd_y(lx,rx,curx,(*it).F.F,-(*it).F.S,(*it).S,X,Y,val);
}
}
else{
if(py[cury].F){
if(!py[cury].S){
ray.insert(iii(ii(ly,-ry),cy));
cy++;
}
}
py[cury].S = 1;
auto it = ray.lower_bound(iii(ii(mid+1,-INF),0));
if(-(*it).F.S <= ry){
upd_y(lx,rx,curx,(*it).F.F,-(*it).F.S,(*it).S,X,Y,val);
}
}
seg[curx][cury] = 0;
auto it = ray.lower_bound(iii(ii(ly,-ry + 1),0));
if(it != ray.end() && -(*it).F.S <= mid){
seg[curx][cury] = __gcd(seg[curx][cury],seg[curx][(*it).S]);
}
it = ray.lower_bound(iii(ii(mid+1,-INF),0));
if(it != ray.end() && -(*it).F.S <= ry){
seg[curx][cury] = __gcd(seg[curx][cury],seg[curx][(*it).S]);
}
}
cout<<lx<<" "<<rx<<" "<<ly<<" "<<ry<<" "<<seg[curx][cury]<<"\n";
}
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].S){
if(!px[curx].F){
rax.insert(iii(ii(lx,-rx),cx));
cx++;
}
}
px[curx].F = 1;
auto it = rax.lower_bound(iii(ii(lx,-rx + 1),0));
if(-(*it).F.S <= mid){
upd_x((*it).F.F,-(*it).F.S,(*it).S,X,Y,val);
}
}
else{
if(px[curx].F){
if(!px[curx].S){
rax.insert(iii(ii(lx,-rx),cx));
cx++;
}
}
px[curx].S = 1;
auto it = rax.lower_bound(iii(ii(mid+1,-INF),0));
if(-(*it).F.S <= rx){
upd_x((*it).F.F,-(*it).F.S,(*it).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;
auto it = ray.lower_bound(iii(ii(ly,-ry + 1),0));
if(it != ray.end()){
ans = __gcd(ans,ask_y(lx,rx,curx,(*it).F.F,-(*it).F.S,(*it).S,X1,X2,Y1,Y2));
}
it = ray.lower_bound(iii(ii(mid+1,-INF),0));
if(it != ray.end()){
ans = __gcd(ans,ask_y(lx,rx,curx,(*it).F.F,-(*it).F.S,(*it).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;
auto it = rax.lower_bound(iii(ii(lx,-rx + 1),0));
if(it != rax.end()){
ans = __gcd(ans,ask_x((*it).F.F,-(*it).F.S,(*it).S,X1,X2,Y1,Y2));
}
it = rax.lower_bound(iii(ii(mid+1,-INF),0));
if(it != rax.end()){
ans = __gcd(ans,ask_x((*it).F.F,-(*it).F.S,(*it).S,X1,X2,Y1,Y2));
}
return ans;
}
void update(int P, int Q, long long K) {
cout<<"update "<<K<<"\n";
if(!evx[P]){
evx[P] = 1;
rax.insert(iii(ii(P,-P),cx));
cx++;
}
if(!evy[Q]){
evy[Q] = 1;
ray.insert(iii(ii(Q,-Q),cy));
cy++;
}
upd_x(0,N-1,0,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return 1;
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
*/