Submission #920603

#	Time	Username	Problem	Language	Result	Execution time	Memory
920603		Macker	Game (IOI13_game)	C++14	63 / 100	5975 ms	256000 KiB

game

#include "game.h"
#include <bits/stdc++.h>

 
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

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

unordered_map<int, unordered_map<int, ll>> st;
int lenx = 1, leny = 1;

ll comb(ll a, ll b){
    if(!a) return b;
    if(!b) return a;
    return gcd2(a, b);
}

ll qry_y(int l, int r, int ix, int i = 1, int s = 0, int e = leny){
    if(l >= e || r <= s) return 0;
    if(l <= s && e <= r){
        return st[ix][i];
    }
    return comb(qry_y(l, r, ix, i * 2, s, (s + e) / 2),
            qry_y(l, r, ix, i * 2 + 1, (s + e) / 2, e));
}

ll qry_x(int l, int ly, int r, int ry, int i = 1, int s = 0, int e = lenx){
    if(l >= e || r <= s) return 0;
    if(l <= s && e <= r){
        return qry_y(ly, ry, i);
    }
    return comb(qry_x(l, ly, r, ry, i * 2, s, (s + e) / 2),
             qry_x(l, ly, r, ry, i * 2 + 1, (s + e) / 2, e));
}

void upd_y(int x, int y, ll val, bool b, int ix, int i = 1, int s = 0, int e = leny){
    if(y >= e || y < s) return;
    if(y == s && s + 1 == e){
        if(b) st[ix][i] = val;
        else st[ix][i] = comb(st[ix * 2][i], st[ix * 2 + 1][i]);
        return;
    }
    upd_y(x, y, val, b, ix, i * 2, s, (s + e) / 2);
    upd_y(x, y, val, b, ix, i * 2 + 1, (s + e) / 2, e);
    st[ix][i] = comb(st[ix][i * 2], st[ix][i * 2 + 1]);
}

void upd_x(int x, int y, ll val, int i = 1, int s = 0, int e = lenx){
    if(x >= e || x < s) return;
    if(x == s && s + 1 == e) {
        upd_y(x, y, val, true, i);
        return;
    }
    upd_x(x, y, val, i * 2, s, (s + e) / 2);
    upd_x(x, y, val, i * 2 + 1, (s + e) / 2, e);
    upd_y(x, y, val, false, i);
}

void init(int R, int C) {
    while(lenx < R) lenx *= 2;
    while(leny < C) leny *= 2;
    //st.resize(2 * lenx, vector<ll>(2 * leny, 0));
}

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

long long calculate(int P, int Q, int U, int V) {
    return qry_x(P, Q, U + 1, V + 1);
}

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