Submission #101866

#	Time	Username	Problem	Language	Result	Execution time	Memory
101866		naoai	Game (IOI13_game)	C++14	63 / 100	4323 ms	257024 KiB

game

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

static int R, C;

int linx, liny;
int linupd, colupd;

i64 query1 (Aint1 *nod, int x, int y, int st, int dr, int a, int b);

Aint2* update2 (Aint2 *nod, int x, int y, int pos, i64 val) {
    if (x == y) {
        nod -> d = val;
        if (linupd - 1 >= linx)
            nod -> d = gcd2(nod -> d, query1(root, 0, R - 1, linx, linupd - 1, colupd, colupd));
        if (linupd + 1 <= liny)
            nod -> d = gcd2(nod -> d, query1(root, 0, R - 1, linupd + 1, liny, colupd, colupd));
        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 = gcd2(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();

    linx = x;
    liny = y;
    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) {
    linupd = P;
    colupd = Q;
    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 (stderr)

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: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20