Submission #756450

#	Time	Username	Problem	Language	Result	Execution time	Memory
756450		alex_2008	Game (IOI13_game)	C++14	63 / 100	1349 ms	246620 KiB

game

#include "game.h"
#include <iostream>
using namespace std;
typedef long long ll;
const ll W = 3000000, WW = 5500000;
ll value[WW];
int ls[WW], rs[WW], lsy[W], rsy[W], root[W];
int sz = 2, sz2 = 2, Root = 1;
int n, m;
ll qans;
ll gcd(ll a, ll b) {
    while (a && b) {
        (a > b) ? a %= b : b %= a;
    }
    return a + b;
}
void queryX(int &v, int C1, int C2, int vleft, int vright) {
    if (v == 0) v = ++sz;
    if (vright < C1 || vleft > C2) return;
    if (vleft >= C1 && vright <= C2) {
        qans = gcd(qans, value[v]);
        return;
    }
    if (ls[v] == 0) {
        qans = gcd(qans, value[v]);
        return;
    }
    int mid = (vleft + vright) / 2;
    queryX(ls[v], C1, C2, vleft, mid);
    queryX(rs[v], C1, C2, mid + 1, vright);
}
void queryY(int &v, int R1, int C1, int R2, int C2, int vleft, int vright) {
    if (v == 0) v = ++sz2;
    if (vleft > R2 || vright < R1) {
        return;
    }
    if (vleft >= R1 && vright <= R2) {
        queryX(root[v], C1, C2, 1, m);
        return;
    }
    int mid = (vleft + vright) / 2;
    queryY(lsy[v], R1, C1, R2, C2, vleft, mid);
    queryY(rsy[v], R1, C1, R2, C2, mid + 1, vright);
}
void Updatex(int &v, int C, ll val, int vleft, int vright) {
    if (v == 0) v = ++sz;
    if (vleft > C || vright < C) return;
    if (vleft == vright) {
        value[v] = val;
        return;
    }
    int mid = (vleft + vright) / 2;
    Updatex(ls[v], C, val, vleft, mid);
    Updatex(rs[v], C, val, mid + 1, vright);
    value[v] = gcd(value[ls[v]], value[rs[v]]);
    return;
}
void Updatey(int &v, int R, int C, ll val, int vleft, int vright) {
    if (v == 0) {
        v = ++sz2;
    }
    if (vleft > R || vright < R) return;
    if (vleft == vright) {
        Updatex(root[v], C, val, 1, m);
        return;
    }
    int mid = (vleft + vright) / 2;
    Updatey(lsy[v], R, C, val, vleft, mid);
    Updatey(rsy[v], R, C, val, mid + 1, vright);
    qans = 0;
    queryX(root[lsy[v]], C, C, 1, m);
    queryX(root[rsy[v]], C, C, 1, m);
    Updatex(root[v], C, qans, 1, m);
}
void init(int R, int C) {
    n = R;
    m = C;
    Root = 1;
}
void update(int R, int Q, long long K) {
    Updatey(Root, R + 1, Q + 1, K, 1, n);
}
long long calculate(int P, int Q, int U, int V) {
    qans = 0;
    queryY(Root, P + 1, Q + 1, U + 1, V + 1, 1, n);
    return qans;
}

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