| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 989357 | User0069 | 게임 (IOI13_game) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=2e5+3;
const int mod=1e9+7;
const int INF=1e18+7;
int n,q,a[maxn],boundr,boundc;
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}
struct segtreetree
{
struct segtree
{
struct node
{
long long val;
node *l,*r;
node(int val): val(val),l(NULL),r(NULL){};
}*root;
long long vall(node* x) {return x?x->val:0;}
void update(node* kk,int cl,int cr,int pos,long long val)
{
if(cl==cr)
{
kk->val=val;
return;
}
int mid=(cl+cr)/2;
if(pos<=mid)
{
if(kk->l==NULL) kk->l=new node(0);
update(kk->l,cl,mid,pos,val);
}
else
{
if(kk->r==NULL) kk->r=new node(0);
update(kk->r,mid+1,cr,pos,val);
}
kk->val=__gcd(vall(kk->l),vall(kk->r));
}
long long get(node* kk,int cl,int cr,int l,int r)
{
if(kk==NULL||cl>r||cr<l) return 0;
if(cl>=l&&cr<=r) return kk->val;
int mid=(cl+cr)/2;
return __gcd(get(kk->l,cl,mid,l,r),get(kk->r,mid+1,cr,l,r));
}
segtree *l, *r;
segtree(): root(new node(0)), l(NULL), r(NULL) {};
}*root;
void update(segtree* kk,int cl,int cr,int r,int c,long long val)
{
if(cl==cr)
{
kk->update(kk->root,0,boundc,c,val);
return;
}
int mid=(cl+cr)/2;
if(r<=mid)
{
if(kk->l==NULL) kk->l=new segtree();
update(kk->l,cl,mid,r,c,val);
}
else
{
if(kk->r==NULL) kk->r=new segtree();
update(kk->r,mid+1,cr,r,c,val);
}
}
int get(segtree *kk,int cl,int cr,int u,int l,int d,int r)
{
if(kk==NULL||cl>d||cr<u) return 0;
if(cl>=u&&cr<=d) return kk->get(kk->root,0,boundc,l,r);
int mid=(cl+cr)/2;
return gcd(get(kk->l,cl,mid,u,l,d,r),get(kk->r,mid+1,cr,u,l,d,r));
}
segtreetree(): root(new segtree()){};
}*root=new segtreetree();
void init(int R,int C)
{
boundr=R-1;
boundc=C-1;
}
void update(int P,int Q, long long k)
{
root->update(root->root,0,boundr,P,Q,k);
}
long long calculate(int P,int Q,int U,int V)
{
return root->get(root->root,0,boundr,P,Q,U,V);
}
//signed main()
//{
// if (fopen(taskname".INP","r"))
// {
// freopen(taskname".INP","r",stdin);
// freopen(taskname".OUT","w",stdout);
// }
// Faster
// init(5,5);
// update(1,1,6);
// update(2,3,8);
// cout<<calculate(1,1,2,3);
//// cout<<gcd(6,8);
//}