#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
ll gcd2(ll,ll);
int R,C;
struct Node{
int s,e;
ll GCD;
Node *LL,*RR,*p;
Node(int s_,int e_):s(s_),e(e_){
GCD=0;
LL=RR=p=NULL;
}
~Node(){
if(LL!=NULL)delete LL;
if(RR!=NULL)delete RR;
}
void up(){
ll z0=0,z1=0;
if(LL!=NULL)z0=LL->GCD;
if(RR!=NULL)z1=RR->GCD;
GCD=gcd2(z0,z1);
}
void update(int x,ll c){
int mid=(s+e)/2;
if(x<s||x>e){
int pL=p->s,pR=p->e,L,R;
L=pL,R=pR;
while(L<=s&&e<=R){
pL=L,pR=R;
mid=(L+R)/2;
if(x<=mid)R=mid;
else L=mid+1;
}
Node* t=new Node(pL,pR);
mid=(p->s+p->e)/2;
if(pR<=mid)p->LL=t;
else p->RR=t;
mid=(pL+pR)/2;
if(x<=mid)t->RR=this;
else t->LL=this;
t->p=p;
p=t;
t->update(x,c);
return;
}
if(s==e){
GCD=c;
return;
}
if(x<=mid){
if(LL==NULL){
LL=new Node(x,x);
LL->p=this;
}
LL->update(x,c);
}
else{
if(RR==NULL){
RR=new Node(x,x);
RR->p=this;
}
RR->update(x,c);
}
up();
}
ll query(int L,int R){
if(e<L||s>R)return 0;
if(L<=s&&e<=R)return GCD;
ll z0=0,z1=0;
if(LL!=NULL)z0=LL->query(L,R);
if(RR!=NULL)z1=RR->query(L,R);
return gcd2(z0,z1);
}
};
struct SegTree{
Node *root;
SegTree(int s=0,int e=0){
root=new Node(s,e);
}
~SegTree(){
delete root;
}
void update(int x,ll c){
root->update(x,c);
}
ll query(int s,int e){
return root->query(s,e);
}
};
struct Node2{
int s,e;
SegTree *tree;
Node2 *LL,*RR,*p;
Node2(int s_,int e_):s(s_),e(e_){
tree=new SegTree(0,R-1);
LL=RR=p=NULL;
}
~Node2(){
if(LL!=NULL)delete LL;
if(RR!=NULL)delete RR;
delete tree;
}
void update(int x,int y,ll c){
int mid=(s+e)/2;
if(x<s||x>e){
int pL=p->s,pR=p->e,L,R;
L=pL,R=pR;
while(L<=s&&e<=R){
pL=L,pR=R;
mid=(L+R)/2;
if(x<=mid)R=mid;
else L=mid+1;
}
Node2* t=new Node2(pL,pR);
mid=(p->s+p->e)/2;
if(pR<=mid)p->LL=t;
else p->RR=t;
mid=(pL+pR)/2;
if(x<=mid)t->RR=this;
else t->LL=this;
t->p=p;
p=t;
t->tree=tree;
t->update(x,y,c);
return;
}
if(s==e){
tree->update(y,c);
return;
}
if(x<=mid){
if(LL==NULL){
LL=new Node2(x,x);
LL->p=this;
}
LL->update(x,y,c);
}
else{
if(RR==NULL){
RR=new Node2(x,x);
RR->p=this;
}
RR->update(x,y,c);
}
ll z0=0,z1=0;
if(LL!=NULL)z0=LL->tree->query(y,y);
if(RR!=NULL)z1=RR->tree->query(y,y);
tree->update(y,gcd2(z0,z1));
}
ll query(int lo,int hi,int L,int R){
if(e<lo||s>hi)return 0;
if(lo<=s&&e<=hi)return tree->query(L,R);
ll z0=0,z1=0;
if(LL!=NULL)z0=LL->query(lo,hi,L,R);
if(RR!=NULL)z1=RR->query(lo,hi,L,R);
return gcd2(z0,z1);
}
};
struct SegTree2{
Node2 *root;
SegTree2(int s=0,int e=0){
root=new Node2(s,e);
}
void finish(){
delete root;
}
void update(int x,int y,ll c){
root->update(x,y,c);
}
ll query(int lo,int hi,int L,int R){
return root->query(lo,hi,L,R);
}
}game;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
void init(int R_, int C_) {
R=R_,C=C_;
game=SegTree2(0,C-1);
}
void update(int P, int Q, long long K) {
game.update(Q,P,K);
}
long long calculate(int P, int Q, int U, int V) {
return game.query(Q,V,P,U);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
1756 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
1756 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
1756 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1756 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
1756 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1756 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
1756 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1756 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
1756 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
1756 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
