Submission #553508

#	Time	Username	Problem	Language	Result	Execution time	Memory
553508		nicholask	Game (IOI13_game)	C++14	0 / 100	2 ms	1236 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
long long gcd(int a,int b){
    while (b) b^=a^=b^=a%=b;
    return a;
}
int n,m;
long long seg[8001][8001];
void updateY(int idX,int tlX,int trX,int idY,int tlY,int trY,int xp,int yp,long long val){
    if (tlY==trY){
        if (tlX==trX) seg[idX][idY]=val;
        else seg[idX][idY]=gcd(seg[2*idX][idY],seg[2*idX+1][idY]);
        return;
    }
    int tm=(tlY+trY)/2;
    if (yp<=tm) updateY(idX,tlX,trX,2*idY,tlY,tm,xp,yp,val);
    else updateY(idX,tlX,trX,2*idY+1,tm+1,trY,xp,yp,val);
    seg[idX][idY]=gcd(seg[idX][2*idY],seg[idX][2*idY+1]);
}
void updateX(int idX,int tlX,int trX,int xp,int yp,long long val){
    if (tlX!=trX){
        int tm=(tlX+trX)/2;
        if (xp<=tm) updateX(2*idX,tlX,tm,xp,yp,val);
        else updateX(2*idX+1,tm+1,trX,xp,yp,val);
    }
    updateY(idX,tlX,trX,1,1,m,xp,yp,val);
}
long long queryY(int idX,int idY,int tlY,int trY,int yps,int ype){
    if (yps>ype) return 0;
    if (yps<=tlY&&trY<=ype) return seg[idX][idY];
    int tm=(tlY+trY)/2;
    long long lx=queryY(idX,2*idY,tlY,tm,yps,min(tm,ype));
    long long rx=queryY(idX,2*idY+1,tm+1,trY,max(yps,tm+1),ype);
    return gcd(lx,rx);
}
long long queryX(int idX,int tlX,int trX,int xps,int xpe,int yps,int ype){
    if (xps>xpe) return 0;
    if (xps<=tlX&&trX<=xpe) return queryY(idX,1,1,m,yps,ype);
    int tm=(tlX+trX)/2;
    long long lx=queryX(2*idX,tlX,tm,xps,min(tm,xpe),yps,ype);
    long long rx=queryX(2*idX+1,tm+1,trX,max(xps,tm+1),xpe,yps,ype);
    return gcd(lx,rx);
}
void init(int R, int C) {
    n=R;
    m=C;
}
 
void update(int P, int Q, long long K) {
    P++; Q++;
    updateX(1,1,n,P,Q,K);
}
 
long long calculate(int P, int Q, int U, int V) {
    P++; Q++; U++; V++;
    return queryX(1,1,n,P,U,Q,V);
}

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