| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 989572 | User0069 | 게임 (IOI13_game) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define taskname "vcl"
#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=1e9+7;
long long n,q,a[maxn],boundr,boundc;
long long gcd(long long a,long long b)
{
if(b==0) return a;
return gcd(b,a%b);
}
struct segtreetree
{
struct segtree
{
struct node
{
long long val;
node *l,*r;
node(long long 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);
}
long long u=0;
if(kk->l) u=kk->l->get(kk->l->root,0,boundc,c,c);
long long v=0;
if(kk->r) v=kk->r->get(kk->r->root,0,boundc,c,c);
kk->update(kk->root,0,boundc,c,gcd(u,v));
}
long long 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"1.OUT","w",stdout);
// }
// Faster
// long long R,C,N;
// cin>>R>>C>>N;
// init(R,C);
// while(N--)
// {
// long long t;
// cin>>t;
// if(t==1)
// {
// long long a,b,c;
// cin>>a>>b>>c;
// update(a,b,c);
// }
// else
// {
// long long a,b,c,d;
// cin>>a>>b>>c>>d;
// cout<<calculate(a,b,c,d)<<"\n";
// }
// }
//// cout<<calculate(2,0,2,0);
//}