제출 #1013201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013201		amirhoseinfar1385	게임 (IOI13_game)	C++17	10 / 100	1811 ms	256000 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100+10,lg=30;
long long all[maxn][maxn],kaf=(1<<lg);
long long gcd(long long a,long long b){
    if(a==0){
        return b;
    }
    if(b==0){
        return a;
    }
    return gcd(b,a%b);
}

struct node{
    long long cl,cr,gc,lnk;
    node(){
        lnk=cl=cr=-1;
        gc=0;
    }
}fake;
vector<node>allnode;
long long te;

void init(int R, int C) {
    //hehe
    te=2;
    allnode.resize(2);
    allnode[0].lnk=1;
}

long long getr(long long u){
    if(allnode[u].cr==-1){
        if(allnode[u].lnk==-1){
            allnode.push_back(fake);
            allnode[u].cr=(long long)allnode.size()-1;
        }else{
            allnode.push_back(fake);
            allnode[u].cr=(long long)allnode.size()-1;
            allnode.back().lnk=(long long)allnode.size();
            allnode.push_back(fake);
        }
    }
    return allnode[u].cr;
}

long long getl(long long u){
    if(allnode[u].cl==-1){
        if(allnode[u].lnk==-1){
            allnode.push_back(fake);
            allnode[u].cl=(long long)allnode.size()-1;
        }else{
            allnode.push_back(fake);
            allnode[u].cl=(long long)allnode.size()-1;
            allnode.back().lnk=(long long)allnode.size();
            allnode.push_back(fake);
        }
    }
    return allnode[u].cl;
}

void asl(long long u1,long long u2,long long u3,long long l,long long r,long long tr,long long w){
    if(l>r||!(tr>=l&&tr<=r)){
        return ;
    }
    allnode[u1].gc=gcd(allnode[u2].gc,allnode[u3].gc);
    if(l==r){
        return;
    }
    long long m=(l+r)>>1;
    asl(getl(u1),getl(u2),getl(u3),l,m,tr,w);
    asl(getr(u1),getr(u2),getr(u3),m+1,r,tr,w);
}

void calc(long long u,long long tr,long long w){
    if(allnode[u].lnk==-1){
        return ;
    }
  //  cout<<"hey1"<<endl;
    long long cl=getl(u);
    long long cr=getr(u);
    asl(allnode[u].lnk,allnode[cl].lnk,allnode[cr].lnk,0,kaf-1,tr,w);
//    cout<<"hey2"<<endl;
}

void upd(long long u,long long l,long long r,long long tl,long long tr,long long w){
    if(l>r||l>tl||r<tl){
        return ;
    }
    if(l==r){
        if(allnode[u].lnk==-1){
     //       cout<<"agab: "<<u<<" "<<l<<" "<<r<<" "<<w<<endl;
            allnode[u].gc=w;
        }else{
            upd(allnode[u].lnk,0,kaf-1,tr,tl,w);
        }
        return ;
    }
    long long m=(l+r)>>1;
    upd(getl(u),l,m,tl,tr,w);
    upd(getr(u),m+1,r,tl,tr,w);
    if(allnode[u].lnk!=-1){
        calc(u,tr,w);
    }else{
        allnode[u].gc=gcd(allnode[getl(u)].gc,allnode[getr(u)].gc);
    }
}

long long pors(long long u,long long l,long long r,long long tl,long long tr,long long tl2,long long tr2){
    if(l>r||l>tr||r<tl||tl>tr){
        return 0;
    }
    if(l>=tl&&r<=tr){
    //    cout<<allnode[u].lnk<<" "<<l<<" "<<r<<" "<<allnode[u].gc<<endl;
        if(allnode[u].lnk==-1){
            return allnode[u].gc;
        }else{
            return pors(allnode[u].lnk,0,kaf-1,tl2,tr2,tl,tr);
        }
    }
    long long m=(l+r)>>1;
    return gcd(pors(getl(u),l,m,tl,tr,tl2,tr2),pors(getr(u),m+1,r,tl,tr,tl2,tr2));
}

void update(int P,int Q, long long K) {
  //  cout<<"manoomadam"<<endl;
    upd(0,0,kaf-1,P,Q,K);
//    cout<<"salam"<<endl;
}

long long calculate(int P,int Q,int U,int V) {
    return pors(0,0,kaf-1,P,U,Q,V);
}

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