제출 #626132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
626132		PoonYaPat	Game (IOI13_game)	C++14	37 / 100	13083 ms	256000 KiB

game

#include "game.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int r,c;
map<pii,ll> s;

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

ll gcd(ll x, ll y) {
    if (x==0) return y;
    if (y==0) return x;
    return gcd2(x,y);
}

void init(int R, int C) {
    r=R;
    c=C;
}

void update_y(int lx, int rx, int idx_x, int ly, int ry, int idx_y, int x, int y, ll val) {
    if (ly>y || ry<y) return;
    if (ly==ry) {
        if (lx==rx) {
            s[pii(idx_x,idx_y)]=val;
        } else {
            s[pii(idx_x,idx_y)]=gcd(s[pii(2*idx_x,idx_y)],s[pii(2*idx_x+1,idx_y)]);
        }
    } else {
        int mid=(ly+ry)/2;
        update_y(lx,rx,idx_x,ly,mid,2*idx_y,x,y,val);
        update_y(lx,rx,idx_x,mid+1,ry,2*idx_y+1,x,y,val);
        s[pii(idx_x,idx_y)]=gcd(s[pii(idx_x,2*idx_y)],s[pii(idx_x,2*idx_y+1)]);
    }
}

void update_x(int lx, int rx, int idx_x, int x, int y, ll val) {
    if (lx>x || rx<x) return;
    if (lx!=rx) {
        int mid=(lx+rx)/2;
        update_x(lx,mid,2*idx_x,x,y,val);
        update_x(mid+1,rx,2*idx_x+1,x,y,val);
    }
    update_y(lx,rx,idx_x,1,c,1,x,y,val);
}

void update(int P, int Q, long long K) {
    ++P; ++Q;
    update_x(1,r,1,P,Q,K);
}

ll query_y(int idx_x, int ly, int ry, int idx_y, int y1, int y2) {
    if (y1>ry || y2<ly) return 0;
    if (y1<=ly && ry<=y2) return s[pii(idx_x,idx_y)];
    int mid=(ly+ry)/2;
    return gcd(query_y(idx_x,ly,mid,2*idx_y,y1,y2),query_y(idx_x,mid+1,ry,2*idx_y+1,y1,y2));
}

ll query_x(int lx, int rx, int idx_x, int x1, int y1, int x2, int y2) {
    if (x1>rx || x2<lx) return 0;
    if (x1<=lx && rx<=x2) return query_y(idx_x,1,c,1,y1,y2);
    int mid=(lx+rx)/2;
    return gcd(query_x(lx,mid,2*idx_x,x1,y1,x2,y2),query_x(mid+1,rx,2*idx_x+1,x1,y1,x2,y2));
}

long long calculate(int P, int Q, int U, int V) {
    ++P; ++Q; ++U; ++V;
    if (P>U) swap(P,U);
    if (Q>V) swap(Q,V);
    return query_x(1,r,1,P,Q,U,V);
}

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