| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1286026 | HoriaHaivas | 게임 (IOI13_game) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
//#include "game.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int range_rng(int l, int r)
{
return uniform_int_distribution<int>(l,r)(rng);
}
const int lim=1e9+5;
struct Node
{
int lson;
int rson;
int gcd;
};
Node emptyNode={0,0,0};
class AINT
{
public:
int sz;
vector<Node> aint;
void init()///de preferat apeleaza asta
{
sz=0;
aint.clear();
aint.push_back(emptyNode);
}
void update(int l, int r, int val, int poz, int x)
{
if (l==r)
{
aint[val].gcd=__gcd(aint[val].gcd,x);
return;
}
int mid;
mid=(l+r)/2;
if (poz<=mid)
{
if (aint[val].lson==0)
{
sz++;
aint[val].lson=sz;
aint.push_back(emptyNode); //aint[sz]=emptyNode;
}
update(l,mid,aint[val].lson,poz,x);
}
else
{
if (aint[val].rson==0)
{
sz++;
aint[val].rson=sz;
aint.push_back(emptyNode); //aint[sz]=emptyNode;
}
update(mid+1,r,aint[val].rson,poz,x);
}
aint[val].gcd=0;
if (aint[val].lson!=0)
aint[val].gcd=__gcd(aint[val].gcd,aint[aint[val].lson].gcd);
if (aint[val].rson!=0)
aint[val].gcd=__gcd(aint[val].gcd,aint[aint[val].rson].gcd);
}
int query(int l, int r, int val, int qa, int qb)
{
if (qa<=l && r<=qb)
{
return aint[val].gcd;
}
int mid,ans;
mid=(l+r)/2;
ans=0;
if (qa<=mid)
{
if (aint[val].lson!=0)
ans=__gcd(ans,query(l,mid,aint[val].lson,qa,qb));
}
if (qb>mid)
{
if (aint[val].rson!=0)
ans=__gcd(ans,query(mid+1,r,aint[val].rson,qa,qb));
}
return ans;
}
};
struct Node_baban
{
AINT a;
int lson;
int rson;
};
Node_baban emptyNode_baban={{0,{emptyNode}},0,0};
class AINT_baban
{
public:
int sz;
vector<Node_baban> aint;
void init()
{
sz=0;
aint.clear();
aint.push_back(emptyNode_baban);
aint.back().a.init();
}
void update(int l, int r, int val, int x, int y, int k)
{
if (l==r)
{
aint[val].a.update(0,lim,0,y,k);
return;
}
int mid;
mid=(l+r)/2;
aint[val].a.update(0,lim,0,y,k);
if (x<=mid)
{
if (aint[val].lson==0)
{
sz++;
aint[val].lson=sz;
aint.push_back(emptyNode_baban);
aint.back().a.init();
}
update(l,mid,aint[val].lson,x,y,k);
}
else
{
if (aint[val].rson==0)
{
sz++;
aint[val].rson=sz;
aint.push_back(emptyNode_baban);
aint.back().a.init();
}
update(mid+1,r,aint[val].rson,x,y,k);
}
}
int query(int l, int r, int val, int x1, int x2, int y1, int y2)
{
if (x1<=l && r<=x2)
{
return aint[val].a.query(0,lim,0,y1,y2);
}
int mid,ans;
mid=(l+r)/2;
ans=0;
if (x1<=mid)
{
if (aint[val].lson!=0)
ans=__gcd(ans,query(l,mid,aint[val].lson,x1,x2,y1,y2));
}
if (x2>mid)
{
if (aint[val].rson!=0)
ans=__gcd(ans,query(mid+1,r,aint[val].rson,x1,x2,y1,y2));
}
return ans;
}
} hurkacz;
void init(signed R, signed C)
{
hurkacz.init();
/*
int i;
for (i=0;i<R;i++)
nush[i].init();
*/
}
void update(signed P, signed Q, long long K)
{
//nush[P].update(0,lim,0,Q,K);
hurkacz.update(0,lim,0,P,Q,K);
}
long long calculate(signed P, signed Q, signed U, signed V)
{
/*
int ans,i;
ans=0;
for (i=P;i<=U;i++)
{
ans=__gcd(ans,nush[i].query(0,lim,0,Q,V));
}
return ans;
*/
return hurkacz.query(0,lim,0,P,U,Q,V);
}
signed main()
{
/*
ifstream fin("camere.in");
ofstream fout("camere.out");
*/
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int r,c,n,i,type,p,q,u,v,k;
cin >> r >> c >> n;
init(r,c);
for (i=1;i<=n;i++)
{
cin >> type;
if (type==1)
{
cin >> p >> q >> k;
update(p,q,k);
}
else
{
cin >> p >> q >> u >> v;
cout << calculate(p,q,u,v) << "\n";
}
}
return 0;
}