제출 #599368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
599368		alirezasamimi100	게임 (IOI13_game)	C++17	63 / 100	4247 ms	256104 KiB

game

#pragma GCC optimize("O0")
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;

long long gcd2(long long X, long long Y) {
    long long tmp;
    if(X<Y) swap(X,Y);
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct n1{
    n1 *lc,*rc;
    ll x;
    n1(){
        lc=rc=nullptr;
        x=0;
    }
};
struct n2{
    n2 *lc,*rc;
    n1 *x;
    n2(){
        lc=rc=nullptr;
        x=new n1;
    }
} *rt=new n2;

int n,m;

void upd1(n1 *v, const int &l, const int &r, const int &p, const ll &x){
    if(r-l==1){
        v->x=x;
        return;
    }
    int m=(l+r)>>1;
    if(p<m){
        if(!v->lc) v->lc=new n1;
        upd1(v->lc,l,m,p,x);
    }else{
        if(!v->rc) v->rc=new n1;
        upd1(v->rc,m,r,p,x);
    }
    v->x=0;
    if(v->lc) v->x=gcd2(v->x,v->lc->x);
    if(v->rc) v->x=gcd2(v->x,v->rc->x);
}

ll get1(n1 *v, const int &l, const int &r, const int &tl, const int &tr){
    if(l>=tr || tl>=r || tl>=tr) return 0;
    if(l>=tl && r<=tr) return v->x;
    int m=(l+r)>>1;
    ll ans=0;
    if(v->lc) ans=gcd2(ans,get1(v->lc,l,m,tl,tr));
    if(v->rc) ans=gcd2(ans,get1(v->rc,m,r,tl,tr));
    return ans;
}

void upd2(n2 *v, const int &l, const int &r, const int &p, const int &q, const ll &x){
    if(r-l==1){
        upd1(v->x,0,m,q,x);
        return;
    }
    int m=(l+r)>>1;
    if(p<m){
        if(!v->lc) v->lc=new n2;
        upd2(v->lc,l,m,p,q,x);
    }else{
        if(!v->rc) v->rc=new n2;
        upd2(v->rc,m,r,p,q,x);
    }
    ll y=0;
    if(v->lc) y=gcd2(y,get1(v->lc->x,0,::m,q,q+1));
    if(v->rc) y=gcd2(y,get1(v->rc->x,0,::m,q,q+1));
    upd1(v->x,0,::m,q,y);
}

ll get2(n2 *v, const int &l, const int &r, const int &tl, const int &tr, const int &tp, const int &tq){
    if(l>=tr || tl>=r || tl>=tr) return 0;
    if(l>=tl && r<=tr) return get1(v->x,0,m,tp,tq);
    int m=(l+r)>>1;
    ll ans=0;
    if(v->lc) ans=gcd2(ans,get2(v->lc,l,m,tl,tr,tp,tq));
    if(v->rc) ans=gcd2(ans,get2(v->rc,m,r,tl,tr,tp,tq));
    return ans;
}

void init(int R, int C) {
    n=R;
    m=C;
}

void update(int p, int q, long long k) {
    upd2(rt,0,n,p,q,k);
}

long long calculate(int p, int q, int u, int v) {
    return get2(rt,0,n,p,u+1,q,v+1);
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20