Submission #698502

#	Time	Username	Problem	Language	Result	Execution time	Memory
698502		vjudge1	Game (IOI13_game)	C++17	0 / 100	0 ms	212 KiB

game

#include <bits/stdc++.h>
#include "game.h"
#define pii pair<int, int>
#define pb push_back
#define gcd __gcd
#define endl "\n"
#define task "CX"
using namespace std;
const int N = 2e3 + 5;
typedef long long ll;
int n, m, q, seg[4 * N][4 * N];
void updy(ll idx, ll idy, ll lx, ll rx, ll ly, ll ry, ll i, ll j, ll val){
    if(ly == ry){
        if(lx == rx) seg[idx][idy] = val;
        else seg[idx][idy] = gcd(seg[idx * 2][idy], seg[idx * 2 + 1][idy]);
    }
    else{
        ll my = (ly + ry) / 2;
        if(j <= my) updy(idx, idy * 2, lx, rx, ly, my, i, j, val);
        else updy(idx, idy * 2 + 1, lx, rx, my + 1, ry, i, j, val);
        seg[idx][idy] = gcd(seg[idx][idy * 2], seg[idx][idy * 2 + 1]);
    }
}
void updx(ll idx, ll tlx, ll trx, ll i, ll j, ll val){
    if(tlx != trx){
        ll mx = (tlx + trx) / 2;
        if(i <= mx) updx(idx * 2, tlx, mx, i, j, val);
        else updx(idx * 2 + 1, mx + 1, trx, i, j, val);
    }
    updy(idx, 1, tlx, trx, 1, m, i, j, val);
}
ll gety(ll idx, ll idy, ll tly, ll tri, ll ly, ll ry){
     if(tri < ly || ry < tly) return 0;
     if(ly <= tly && tri <= ry){ return seg[idx][idy]; }
     ll my = (tly + tri) / 2;
     return gcd(gety(idx, idy * 2, tly, my, ly, ry), gety(idx, idy * 2 + 1, my + 1, tri, ly, ry));
}

ll getx(ll idx, ll tlx, ll trx, ll lx, ll rx, ll ly, ll ry){
    if(rx < tlx || trx < lx) return 0;
    if(lx <= tlx && trx <= rx){ return gety(idx, 1, 1, m, ly, ry); }
    ll mx = (tlx + trx) / 2;
    return gcd(getx(idx * 2, tlx, mx, lx, rx, ly, ry), getx(idx * 2 + 1, mx + 1, trx, lx, rx, ly, ry));
}
void init(int R, int C){
    n = R; m = C;
}
void update(int P, int Q, long long K){
    ++P; ++Q;
    updx(1, 1, n, P, Q, K);
}
long long calculate(int P, int Q, int U, int V){
    ++P; ++U; ++Q; ++V;
    return getx(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