Submission #1040247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040247		ArthuroWich	Game (IOI13_game)	C++17	36 / 100	810 ms	139140 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int gcd2(int X, int Y) {
    int tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
int seg[4*2005][4*2005];
void updatey(int nx, int ny, int l, int r, int lx, int rx, int y, int v) {
    if (l == r) {
        if (lx == rx) {
            seg[nx][ny] = v;
        } else {
            seg[nx][ny] = gcd2(seg[2*nx][ny], seg[2*nx+1][ny]);
        }
    } else {
        int m = (l+r)/2;
        if (l <= y && y <= m) {
            updatey(nx, 2*ny, l, m, lx, rx, y, v);
        } else {
            updatey(nx, 2*ny+1, m+1, r, lx, rx, y, v);
        }
        seg[nx][ny] = gcd2(seg[nx][2*ny], seg[nx][2*ny+1]);
    }
}
void updatex(int nx, int l, int r, int x, int y, int v) {
    if (l != r) {
        int m = (l+r)/2;
        if (l <= x && x <= m) {
            updatex(2*nx, l, m, x, y, v);
        } else {
            updatex(2*nx+1, m+1, r, x, y, v);
        }
        seg[nx][1] = gcd2(seg[2*nx][1], seg[2*nx+1][1]);
    }
    updatey(nx, 1, 0, 2000, l, r, y, v);
}
int queryy(int nx, int ny, int l, int r, int ay, int by) {
    if (by < l || r < ay) {
        return 0;
    } else if (ay <= l && r <= by) {
        return seg[nx][ny];
    } else {
        int m = (l+r)/2;
        return gcd2(queryy(nx, 2*ny, l, m, ay, by), queryy(nx, 2*ny+1, m+1, r, ay, by));
    }
}
int queryx(int nx, int l, int r, int ax, int bx, int ay, int by) {
    if (bx < l || r < ax) {
        return 0;
    } else if (ax <= l && r <= bx) {
        return queryy(nx, 1, 0, 2000, ay, by);
    } else {
        int m = (l+r)/2;
        return gcd2(queryx(2*nx, l, m, ax, bx, ay, by), queryx(2*nx+1, m+1, r, ax, bx, ay, by));
    }
}
void init(int32_t R, int32_t C) {

}
void update(int32_t P, int32_t Q, int K) {
    updatex(1, 0, 2000, P, Q, K);
}
int calculate(int32_t P, int32_t Q, int32_t U, int32_t V) {
    return queryx(1, 0, 2000, P, U, Q, V);
}

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