Submission #60764

#	Time	Username	Problem	Language	Result	Execution time	Memory
60764		aome	게임 (IOI13_game)	C++14	63 / 100	3045 ms	257024 KiB

game

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

using namespace std;

#define mid ((l + r) >> 1)

struct NodeY {
    long long gcd;
    NodeY *l, *r;

    NodeY() : l(NULL), r(NULL), gcd(0) {}
};

struct NodeX {
    int l, r;
    NodeY *v;

    NodeX() : l(0), r(0), v(NULL) {}
} a[70005];

int cnt = 1;
int R, C;
int P, Q, U, V;
long long K;
long long res;

void init(int _R, int _C) {
    R = _R, C = _C;
}

void getY(NodeY *i, int l, int r) {
    if (!i) return;
    if (l > V || U > r) return;
    if (U <= l && r <= V) {
        res = __gcd(res, i -> gcd); return;
    }
    getY(i -> l, l, mid);
    getY(i -> r, mid + 1, r);
}

void getX(int i, int l, int r) {
    if (!i) return;
    if (l > Q || P > r) return;
    if (P <= l && r <= Q) {
        getY(a[i].v, 0, C - 1); return;
    }
    getX(a[i].l, l, mid);
    getX(a[i].r, mid + 1, r);
}

void updateY(NodeY *i, int l, int r) {
    if (l == r) {
        i -> gcd = K; return;
    }
    if (mid >= Q) {
        if (!(i -> l)) i -> l = new NodeY();
        updateY(i -> l, l, mid);
    }
    else {
        if (!(i -> r)) i -> r = new NodeY();
        updateY(i -> r, mid + 1, r);
    }
    long long vl = (!(i -> l) ? 0 : i -> l -> gcd);
    long long vr = (!(i -> r) ? 0 : i -> r -> gcd);
    i -> gcd = __gcd(vl, vr);
}

void updateX(int i, int l, int r) {
    if (l == r) {
        if (!(a[i].v)) a[i].v = new NodeY();
        updateY(a[i].v, 0, C - 1); 
        return;
    }
    if (mid >= P) {
        if (!(a[i].l)) a[i].l = ++cnt;
        updateX(a[i].l, l, mid);
        res = 0;
        if (a[i].r) {
            getY(a[a[i].r].v, 0, C - 1);
        }
        K = __gcd(K, res);
    }
    else {
        if (!(a[i].r)) a[i].r = ++cnt;
        updateX(a[i].r, mid + 1, r);
        res = 0;
        if (a[i].l) {
            getY(a[a[i].l].v, 0, C - 1);
        }
        K = __gcd(K, res);
    }
    if (!(a[i].v)) a[i].v = new NodeY();
    updateY(a[i].v, 0, C - 1);
}

void update(int _P, int _Q, long long _K) {
    P = _P, Q = U = V = _Q, K = _K;
    updateX(1, 0, R - 1);
}

long long calculate(int _P, int _U, int _Q, int _V) {
    res = 0;
    P = _P, Q = _Q, U = _U, V = _V;
    getX(1, 0, R - 1);
    return res;
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
game.cpp: In constructor 'NodeY::NodeY()':
game.cpp:10:16: warning: 'NodeY::r' will be initialized after [-Wreorder]
     NodeY *l, *r;
                ^
game.cpp:9:15: warning:   'long long int NodeY::gcd' [-Wreorder]
     long long gcd;
               ^~~
game.cpp:12:5: warning:   when initialized here [-Wreorder]
     NodeY() : l(NULL), r(NULL), gcd(0) {}
     ^~~~~

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