Submission #599954

#	Time	Username	Problem	Language	Result	Execution time	Memory
599954		AmirElarbi	Game (IOI13_game)	C++14	0 / 100	1 ms	308 KiB

game

#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 2e9+5
#define eps 1e-7
#define eps1 1e-25
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
using namespace std;
const int MOD = 1e9;
const int nax = 2e3+5;
#include "game.h"
int n,m, t[nax*4][nax*4];
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;
}

int gcd_y(int vx, int vy, int tly, int try_, int ly, int ry) {
    if (ly > ry) 
        return 0;
    if (ly == tly && try_ == ry)
        return t[vx][vy];
    int tmy = (tly + try_) / 2;
    return gcd2( gcd_y(vx, vy*2, tly, tmy, ly, min(ry, tmy))
         , gcd_y(vx, vy*2+1, tmy+1, try_, max(ly, tmy+1), ry));
}

int gcd_x(int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
    if (lx > rx)
        return 0;
    if (lx == tlx && trx == rx)
        return gcd_y(vx, 1, 0, m-1, ly, ry);
    int tmx = (tlx + trx) / 2;
    return gcd2(gcd_x(vx*2, tlx, tmx, lx, min(rx, tmx), ly, ry)
         , gcd_x(vx*2+1, tmx+1, trx, max(lx, tmx+1), rx, ly, ry));
}

void update_y(int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, int new_val) {
    if (ly == ry) {
        if (lx == rx)
            t[vx][vy] = new_val;
        else
            t[vx][vy] = gcd2(t[vx*2][vy] , t[vx*2+1][vy]);
    } else {
        int my = (ly + ry) / 2;
        if (y <= my)
            update_y(vx, lx, rx, vy*2, ly, my, x, y, new_val);
        else
            update_y(vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
        t[vx][vy] = gcd2(t[vx][vy*2] , t[vx][vy*2+1]);
    }
}

void update_x(int vx, int lx, int rx, int x, int y, int new_val) {
    if (lx != rx) {
        int mx = (lx + rx) / 2;
        if (x <= mx)
            update_x(vx*2, lx, mx, x, y, new_val);
        else
            update_x(vx*2+1, mx+1, rx, x, y, new_val);
    }
    update_y(vx, lx, rx, 1, 0, m-1, x, y, new_val);
}

void init(int R, int C) {
    n = R, m = C;
}

void update(int P, int Q, long long K) {
    update_x(1,0,n-1,P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    return gcd_x(1,0,n-1,P,U,Q,V);
}

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