Submission #15777

#	Time	Username	Problem	Language	Result	Execution time	Memory
15777		ainta	Game (IOI13_game)	C++98	63 / 100	3425 ms	256000 KiB

game

#include "game.h"
#include<stdio.h>
#include<algorithm>
using namespace std;

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;
}

struct SegY{
    long long G;
    SegY *c1, *c2;
    SegY(){
        G=0;
        c1=c2=NULL;
    }
};

struct SegX{
    long long G;
    SegX *c1, *c2;
    SegY *cy;
    SegX(){
        G=0;
        c1=c2=NULL;
        cy=NULL;
    }
};

SegX *rootX;
SegY *rootY;

int MR, MC;



void init(int R, int C) {
    rootX = new SegX();
    rootY = new SegY();
    MR = R, MC = C;
}

void InsY(SegY *nd, int b, int e, int y, long long K){
    if(b==e){
        nd->G = K;
        return;
    }
    int m = (b+e)>>1;
    if(!nd->c1){
        nd->c1 = new SegY();
        nd->c2 = new SegY();
    }
    if(y <= m)InsY(nd->c1, b, m, y, K);
    else InsY(nd->c2, m+1, e, y, K);
    nd->G = gcd2(nd->c1->G, nd->c2->G);
}

void UDT(SegY *nd, SegY *nd1, SegY *nd2, int b, int e, int y){
    nd->G = gcd2(nd1?nd1->G:0, nd2?nd2->G:0);
    if(b==e)return;
    int m = (b+e)>>1;
    if(!nd->c1)nd->c1 = new SegY(), nd->c2 = new SegY();
    if(y <= m)UDT(nd->c1, nd1?nd1->c1:NULL, nd2?nd2->c1:NULL, b, m, y);
    else UDT(nd->c2, nd1?nd1->c2:NULL, nd2?nd2->c2:NULL, m+1, e, y);
}

void InsX(SegX *nd, int b, int e, int x, int y, long long K){
    if(b==e){
        if(!nd->cy)nd->cy = new SegY();
        InsY(nd->cy, 0, MC - 1, y, K);
        return;
    }
    int m = (b+e)>>1;
    if(!nd->c1)nd->c1 = new SegX(), nd->c2 = new SegX();
    if(!nd->cy)nd->cy = new SegY();
    if(x <= m) InsX(nd->c1, b, m, x, y, K);
    else InsX(nd->c2, m+1, e, x, y, K);
    UDT(nd->cy, nd->c1->cy, nd->c2->cy, 0, MC - 1, y);
}

void update(int P, int Q, long long K) {
    InsX(rootX, 0, MR - 1, P, Q, K);
}

long long CalcY(SegY *nd, int b, int e, int s, int l){
    if(!nd)return 0;
    if(b == s && e == l)return nd->G;
    int m = (b+e)>>1;
    long long r = 0;
    if(s <= m && nd->c1) r = CalcY(nd->c1, b, m, s, min(m,l));
    if(l > m && nd->c2) r = gcd2(CalcY(nd->c2, m + 1, e, max(s, m+1), l), r);
    return r;
}

long long CalcX(SegX *nd, int b, int e, int s, int l, int by, int ey){
    if(b == s && e == l)return CalcY(nd->cy, 0, MC - 1, by, ey);
    int m = (b+e)>>1;
    long long r = 0;
    if(s <= m && nd->c1) r = CalcX(nd->c1, b, m, s, min(m,l), by, ey);
    if(l > m && nd->c2) r = gcd2(CalcX(nd->c2, m+1, e, max(m+1, s), l, by, ey), r);
    return r;
}

long long calculate(int P, int Q, int U, int V) {
    return CalcX(rootX, 0, MR - 1, P, U, Q, V);
}

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