Submission #1165574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165574		HappyCapybara	Game (IOI13_game)	C++20	63 / 100	1088 ms	136248 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

int r, c;
vector<vector<ll>> st;

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

void change(int x, int y, ll val){
    int txl = 0, txr = r-1, tyl = 0, tyr = c-1, nx = 1, ny = 1;
    while (txl != txr){
        int txm = (txl+txr)/2;
        if (x <= txm){
            nx = nx*2;
            txr = txm;
        }
        else {
            nx = nx*2+1;
            txl = txm+1;
        }
    }
    while (tyl != tyr){
        int tym = (tyl+tyr)/2;
        if (y <= tym){
            ny = ny*2;
            tyr = tym;
        }
        else {
            ny = ny*2+1;
            tyl = tym+1;
        }
    }
    //cout << x << " " << y << " " << txl << " " << tyl << " " << nx << " " << ny << endl;
    st[nx][ny] = val;
    int cnx = nx;
    while (cnx){
        if (cnx != nx) st[cnx][ny] = gcd2(st[cnx*2][ny], st[cnx*2+1][ny]);
        int cny = ny>>1;
        while (cny){
            st[cnx][cny] = gcd2(st[cnx][cny*2], st[cnx][cny*2+1]);
            cny >>= 1;
        }
        cnx >>= 1;
    }
}

ll queryh(int hn, int y1, int y2, int node=1, int tl=0, int tr=c-1){
    if (y1 <= tl && tr <= y2) return st[hn][node];
    int tm = (tl+tr)/2;
    ll res = 0;
    if (y1 <= tm) res = gcd2(res, queryh(hn, y1, y2, node*2, tl, tm));
    if (tm+1 <= y2) res = gcd2(res, queryh(hn, y1, y2, node*2+1, tm+1, tr));
    return res;
}

ll queryv(int x1, int x2, int y1, int y2, int node=1, int tl=0, int tr=r-1){
    if (x1 <= tl && tr <= x2) return queryh(node, y1, y2);
    int tm = (tl+tr)/2;
    ll res = 0;
    if (x1 <= tm) res = gcd2(res, queryv(x1, x2, y1, y2, node*2, tl, tm));
    if (tm+1 <= x2) res = gcd2(res, queryv(x1, x2, y1, y2, node*2+1, tm+1, tr));
    return res;
}

void init(int R, int C) {
    r = R;
    c = C;
    if (R > 10) st.resize(4100, vector<ll>(4100, 0));
    else st.resize(4*R, vector<ll>(4*C, 0));
}

void update(int P, int Q, long long K) {
    change(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return queryv(P, U, Q, V);
}

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