oj.uz

Submission #101732

# Submission time Handle Problem Language Result Execution time Memory
101732 2019-03-19T16:34:18 Z naoai Game (IOI13_game) C++14
0 / 100
 3 ms 512 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long i64;

struct Aint2 {
    i64 d;
    Aint2 *st, *dr;

    Aint2 () {
        d = 0;
        st = dr = NULL;
    }
};

struct Aint1 {
    Aint2 *rep;
    Aint1 *st, *dr;

    Aint1 () {
        rep = NULL;
        st = dr = NULL;
    }
} *root;

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

int R, C;

Aint2* update2 (Aint2 *nod, int x, int y, int pos, i64 val) {
    if (x == y) {
        nod -> d = val;
        return nod;
    }

    int mij = (x + y) / 2;
    if (pos <= mij) {
        if (nod -> st == NULL)
            nod -> st = new Aint2();
        nod -> st = update2(nod -> st, x, mij, pos, val);
    } else {
        if (nod -> dr == NULL)
            nod -> dr = new Aint2();
        nod -> dr = update2(nod -> dr, mij + 1, y, pos, val);
    }

    nod -> d = 0;
    if (nod -> st != NULL) nod -> d = nod -> st -> d;
    if (nod -> dr != NULL) nod -> d = gcd2(nod -> d, nod -> dr -> d);
    return nod;
}

i64 query2 (Aint2 *nod, int x, int y, int st, int dr) {
    if (nod == NULL)
        return 0;
    if (st <= x && y <= dr)
        return nod -> d;

    int mij = (x + y) / 2;
    i64 ans = 0;

    if (st <= mij)
        ans = gcd2(ans, query2(nod -> st, x, mij, st, dr));
    if (mij < dr)
        ans = gcd2(ans, query2(nod -> dr, mij + 1, y, st, dr));
    return ans;
}

Aint1* update1 (Aint1 *nod, int x, int y, int r, int c, i64 val) {
    if (nod -> rep == NULL)
        nod -> rep = new Aint2();
    nod -> rep = update2(nod -> rep, 0, C - 1, c, val);

    if (x == y) {
        return nod;
    }

    int mij = (x + y) / 2;
    if (r <= mij) {
        if (nod -> st == NULL)
            nod -> st = new Aint1();
        nod -> st = update1(nod -> st, x, mij, r, c, val);
    } else {
        if (nod -> dr == NULL)
            nod -> dr = new Aint1();
        nod -> dr = update1(nod -> dr, mij + 1, y, r, c, val);
    }

    return nod;
}

i64 query1 (Aint1 *nod, int x, int y, int st, int dr, int a, int b) {
    if (nod == NULL)
        return 0;

    if (st <= x && y <= dr)
        return query2(nod -> rep, 0, C - 1, a, b);

    int mij = (x + y) / 2;
    i64 ans = 0;
    if (st <= mij)
        ans = gcd2(ans, query1(nod -> st, x, mij, st, dr, a, b));
    if (mij < dr)
        ans = gcd2(ans, query1(nod -> dr, mij + 1, y, st, dr, a, b));
    return ans;
}

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

    root = new Aint1();
}

void update(int P, int Q, long long K) {
    root = update1(root, 0, R - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return query1(root, 0, R - 1, P, U, Q, V);
}

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;
      ^~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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