oj.uz

답안 #60715

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
60715 2018-07-24T15:07:20 Z aome 게임 (IOI13_game) C++14
0 / 100
 5 ms 868 KB 
#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 {
    NodeX *l, *r;
    NodeY *v;

    NodeX() : l(NULL), r(NULL), v(NULL) {}
};

int R, C;
int P, Q, U, V;
long long K;
long long res;
NodeX *root;

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

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);
    }
    int vl = (!(i -> l) ? 0 : i -> l -> gcd);
    int vr = (!(i -> r) ? 0 : i -> r -> gcd);
    i -> gcd = __gcd(vl, vr);
    // cout << "#updateY " << l << ' ' << r << ' ' << i -> gcd << '\n';
}

void updateX(NodeX *i, int l, int r) {
    if (!(i -> v)) {
        i -> v = new NodeY();
    }
    // cout << "#updateX " << l << ' ' << r << '\n'; 
    updateY(i -> v, 0, C - 1);
    if (l == r) return;
    if (mid >= P) {
        if (!(i -> l)) i -> l = new NodeX();
        updateX(i -> l, l, mid);
    }
    else {
        if (!(i -> r)) i -> r = new NodeX();
        updateX(i -> r, mid + 1, r);
    }
}

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

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(NodeX *i, int l, int r) {
    if (!i) return;
    if (l > Q || P > r) return;
    if (P <= l && r <= Q) {
        getY(i -> v, 0, C - 1); return;
    }
    getX(i -> l, l, mid);
    getX(i -> r, mid + 1, r);
}

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

Compilation message

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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 5 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 480 KB Output is correct
2 Incorrect 2 ms 572 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 572 KB Output is correct
2 Incorrect 4 ms 756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 756 KB Output is correct
2 Incorrect 3 ms 756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 756 KB Output is correct
2 Incorrect 3 ms 868 KB Output isn't correct
3 Halted 0 ms 0 KB -