#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct Tnode
{
long long a;
Tnode *l, *r;
Tnode()
{
a = 0;
l = r = nullptr;
}
};
struct Tree
{
Tnode *A;
Tree *L, *R;
Tree()
{
A = nullptr;
L = R = nullptr;
}
};
Tree *Root;
int r,c;
int Ql,Qr,ql,qr;
int Pos,pos,val;
long long gcd3(long long a, long long b)
{
while(a&&b)
{
if(a>b) a %= b;
else b %= a;
}
return a+b;
}
long long merge1(Tnode *&t1, Tnode *&t2)
{
//if(t1==nullptr&&t2==nullptr) return 0;
if(t1==nullptr) return t2->a;
if(t2==nullptr) return t1->a;
return gcd3(t1->a,t2->a);
}
void upd(Tnode *&t, int l, int r)
{
if(t==nullptr) t = new Tnode();
if(l==r)
{
t->a = val;
return;
}
int mid = (l+r)/2;
if(mid<=pos) upd(t->l,l,mid+0);
else upd(t->r,mid+1,r);
t->a = merge1(t->l,t->r);
}
Tnode *getA(Tree *&t)
{
if(t==nullptr) return nullptr;
return t->A;
}
long long geta(Tnode *&t)
{
if(t==nullptr) return 0;
return (t->a);
}
void Merge(Tnode *&t, Tnode *t1, Tnode *t2, int l, int r)
{
if(t==nullptr) t = new Tnode();
if(l==r)
{
t->a = gcd3(geta(t1),geta(t2));
return;
}
int mid = (l+r)/2;
if(mid<=pos) Merge(t->l,t1->l,t2->l,l,mid+0);
else Merge(t->r,t1->r,t2->r,mid+1,r);
t->a = gcd3(geta(t->l),geta(t->r));
}
void Upd(Tree *&t, int l, int r)
{
if(t==nullptr) t = new Tree();
if(l==r)
{
upd(t->A,0,c-1);
return;
}
int mid = (l+r)/2;
if(Pos<=mid) Upd(t->L,l,mid+0);
else Upd(t->R,mid+1,r);
Merge(t->A,getA(t->L),getA(t->R),0,c-1);
}
void update(int P, int Q, long long K)
{
Pos = P;
pos = Q;
val = K;
Upd(Root,0,r-1);
}
long long query(Tnode *&t, int l, int r)
{
if(r<ql||qr<l||l>r) return -1;
if(t==nullptr) return 0;
if(ql<=l&&r<=qr) return t->a;
int mid = (l+r)/2;
long long ch1 = query(t->l,l,mid+0);
long long ch2 = query(t->r,mid+1,r);
if(ch1==-1) return ch2;
if(ch2==-1) return ch1;
return gcd3(ch1,ch2);
}
long long Query(Tree *&t, int l, int r)
{
if(r<Ql||Qr<l||l>r) return -1;
if(t==nullptr) return 0;
if(Ql<=l&&r<=Qr) return query(t->A,0,c-1);
int mid = (l+r)/2;
long long ch1 = Query(t->L,l,mid+0);
long long ch2 = Query(t->R,mid+1,r);
if(ch1==-1) return ch2;
if(ch2==-1) return ch1;
return gcd3(ch1,ch2);
}
long long calculate(int P, int Q, int U, int V)
{
ql = Q;
qr = V;
///
Ql = P;
Qr = U;
long long ans = Query(Root,0,r-1);
if(ans==-1) ans = 0;
return ans;
}
void init(int R, int C)
{
r = R;
c = C;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |