Submission #46938

#	Time	Username	Problem	Language	Result	Execution time	Memory
46938		RayaBurong25_1	Game (IOI13_game)	C++17	0 / 100	3 ms	704 KiB

game

#include "game.h"
#include <stdio.h>
#include <cassert>
typedef struct nodeX nodeX;
typedef struct nodeY nodeY;
struct nodeX
{
    nodeX* l = NULL;
    nodeX* r = NULL;
    nodeY* y = NULL;
};
struct nodeY
{
    long long v;
    nodeY* l = NULL;
    nodeY* r = NULL;
};
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 maxR, maxC;
nodeX* root;
void init(int R, int C)
{
    maxR = R;
    maxC = C;
    root = new nodeX();
}
void updateY(nodeY* p, int Q, long long K, int sY, int eY)
{
    // printf("updateY %p %d %lld %d %d\n", p, Q, K, sY, eY);
    if (sY == eY)
    {
        p->v = K;
        return;
    }
    int m = (sY + eY)/2;
    if (Q <= m)
    {
        if (p->l == NULL)
            p->l = new nodeY();
        updateY(p->l, Q, K, sY, m);
    }
    else
    {
        if (p->r == NULL)
            p->r = new nodeY();
        updateY(p->r, Q, K, m + 1, eY);
    }
    if (p->l == NULL && p->r == NULL)
        assert(1 == 0);
    else if (p->l == NULL)
        p->v = p->r->v;
    else if (p->r == NULL)
        p->v = p->l->v;
    else
        p->v = gcd2(p->l->v, p->r->v);
}
void updateX(nodeX* p, int P, int Q, long long K, int sX, int eX)
{
    // printf("updateX %p %d %d %lld %d %d\n", p, P, Q, K, sX, eX);
    if (sX == eX)
    {
        if (p->y == NULL)
            p->y = new nodeY();
        updateY(p->y, Q, K, 0, maxC);
        return;
    }
    int m = (sX + eX)/2;
    if (P <= m)
    {
        if (p->l == NULL)
            p->l = new nodeX();
        updateX(p->l, P, Q, K, sX, m);
    }
    else
    {
        if (p->r == NULL)
            p->r = new nodeX();
        updateX(p->r, P, Q, K, m + 1, eX);
    }
    if (p->y == NULL)
        p->y = new nodeY();
    updateY(p->y, Q, K, 0, maxC);
}
void update(int P, int Q, long long K)
{
    updateX(root, P, Q, K, 0, maxR);
}
int min(int a, int b)
{
    return (a < b)?a:b;
}
int max(int a, int b)
{
    return (a > b)?a:b;
}
long long queryY(nodeY* p, int qsY, int qeY, int sY, int eY)
{
    // printf("queryY %p %d %d %d %d\n", p, qsY, qeY, sY, eY);
    if (qsY == sY && qeY == eY)
        return p->v;
    int m = (sY + eY)/2;
    long long r = 0;
    if (qsY <= m)
        r = gcd2(r, queryY(p->l, qsY, min(qeY, m), sY, m));
    if (qeY >= m + 1)
        r = gcd2(r, queryY(p->r, max(qsY, m + 1), qeY, m + 1, eY));
    return r;
}
long long queryX(nodeX* p, int qsX, int qeX, int qsY, int qeY, int sX, int eX)
{
    // printf("queryX %p %d %d %d %d %d %d\n", p, qsX, qeX, qsY, qeY, sX, eX);
    if (qsX == sX && qeX == eX)
        return queryY(p->y, qsY, qeY, 0, maxC);
    int m = (sX + eX)/2;
    long long r = 0;
    if (qsX <= m)
        r = gcd2(r, queryX(p->l, qsX, min(qeX, m), qsY, qeY, sX, m));
    if (qeX >= m + 1)
        r = gcd2(r, queryX(p->r, max(qsX, m + 1), qeX, qsY, qeY, m + 1, eX));
    return r;
}
long long calculate(int P, int Q, int U, int V)
{
    return queryX(root, P, U, Q, V, 0, maxR);
}

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