oj.uz

Submission #60736

# Submission time Handle Problem Language Result Execution time Memory
60736 2018-07-24T15:43:30 Z aome Game (IOI13_game) C++14
0 / 100
 3 ms 536 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 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);
}

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(NodeX *i, int l, int r) {
    if (!(i -> v)) {
        i -> v = new NodeY();
        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);
        res = 0;
        if (i -> r) {
            getY(i -> r -> v, 0, C - 1);
        }
        K = __gcd(K, res);
    }
    else {
        if (!(i -> r)) i -> r = new NodeX();
        updateX(i -> r, mid + 1, r);
        res = 0;
        if (i -> l) {
            getY(i -> l -> v, 0, C - 1);
        }
        K = __gcd(K, res);
    }
    if (!(i -> v)) i -> v = new NodeY();
    updateY(i -> v, 0, C - 1);
}

void update(int _P, int _Q, long long _K) {
    P = _P, Q = U = V = _Q, K = _K;
    updateX(root, 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(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

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 536 KB Output isn't correct
2 Halted 0 ms 0 KB -