Submission #553664

#	Time	Username	Problem	Language	Result	Execution time	Memory
553664		nicholask	Game (IOI13_game)	C++14	0 / 100	1 ms	340 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
struct smallnode{
    smallnode *lc,*rc;
    long long val;
    int from;
    smallnode(){
        lc=rc=nullptr;
        val=0;
        from=-1;
    }
    smallnode(int From,long long Val){
        lc=rc=nullptr;
        from=From;
        val=Val;
    }
};
struct bignode{
    bignode *lc,*rc;
    smallnode *down;
    long long val;
    bignode(){
        lc=rc=nullptr;
        down=nullptr;
        val=0;
    }
};
bignode *root;
long long gcd(long long a,long long b){
    while (b) b^=a^=b^=a%=b;
    return a;
}
int n,m;
void init(int R,int C){
    root=new bignode;
    n=R;
    m=C;
}
void pushdown(smallnode *id,int tlY,int trY){
    if (!id||id->from<0) return;
    int tmY=(tlY+trY)/2;
    if (id->from<=tmY) id->lc=new smallnode(id->from,id->val);
    else id->rc=new smallnode(id->from,id->val);
    id->from=-1226;
}
long long queryY(smallnode *id,int tlY,int trY,int lY,int rY){
    if (!id||lY>rY) return 0ll;
    if (lY<=tlY&&trY<=rY) return id->val;
    if (tlY<=id->from&&id->from<=trY) return id->val;
    if (id->from>=0) return 0ll;
    int tmY=(tlY+trY)/2;
    long long lans=(id->lc?queryY(id->lc,tlY,tmY,lY,min(rY,tmY)):0ll);
    long long rans=(id->rc?queryY(id->rc,tmY+1,trY,max(lY,tmY+1),rY):0ll);
    return gcd(lans,rans);
}
long long queryX(bignode *id,int tlX,int trX,int lX,int rX,int lY,int rY){
    if (!id||lX>rX) return 0ll;
    if (lX<=tlX&&trX<=rX) return queryY(id->down,1,m,lY,rY);
    int tmX=(tlX+trX)/2;
    long long lans=(id->lc?queryX(id->lc,tlX,tmX,lX,min(rX,tmX),lY,rY):0ll);
    long long rans=(id->rc?queryX(id->rc,tmX+1,trX,max(lX,tmX+1),rX,lY,rY):0ll);
    return gcd(lans,rans);
}
void updateY(smallnode *id,int tlY,int trY,int yp,long long Val){
    if (!id) return;
    if (id->from==-1){
        id->from=yp;
        id->val=Val;
        return;
    }
    if (id->from==yp){
        id->val=Val;
        return;
    }
    pushdown(id,tlY,trY);
    if (tlY==trY){
        id->val=Val;
        return;
    }
    int tmY=(tlY+trY)/2;
    if (yp<=tmY){
        if (!id->lc) id->lc=new smallnode;
        updateY(id->lc,tlY,tmY,yp,Val);
    } else {
        if (!id->rc) id->rc=new smallnode;
        updateY(id->rc,tmY+1,trY,yp,Val);
    }
    long long lans=(id->lc?id->lc->val:0ll);
    long long rans=(id->rc?id->rc->val:0ll);
    id->val=gcd(lans,rans);
}
void updateX(bignode *id,int tlX,int trX,int xp,int yp,long long Val){
    if (!id->down) id->down=new smallnode;
    if (tlX==trX){
        updateY(id->down,1,m,yp,Val);
        return;
    }
    int tmX=(tlX+trX)/2;
    if (xp<=tmX){
        if (!id->lc) id->lc=new bignode;
        updateX(id->lc,tlX,tmX,xp,yp,Val);
    } else {
        if (!id->rc) id->rc=new bignode;
        updateX(id->rc,tmX+1,trX,xp,yp,Val);
    }
    long long lans=(id->lc?queryY(id->lc->down,1,m,yp,yp):0ll);
    long long rans=(id->rc?queryY(id->rc->down,1,m,yp,yp):0ll);
    updateY(id->down,1,m,yp,gcd(lans,rans));
}
void update(int P,int Q,long long K){
    updateX(root,1,n,P+1,Q+1,K);
}
long long calculate(int P,int Q,int U,int V){
    return queryX(root,1,n,P+1,U+1,Q+1,V+1);
}

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