oj.uz

Submission #46944

# Submission time Handle Problem Language Result Execution time Memory
46944 2018-04-25T10:04:50 Z RayaBurong25_1 Game (IOI13_game) C++14
63 / 100
 13000 ms 256000 KB 
#include "game.h"
#include <stdio.h>
#include <cassert>
typedef struct nodeX nodeX;
typedef struct nodeY nodeY;
struct nodeX
{
    nodeX* l;
    nodeX* r;
    nodeY* y;
    nodeX()
    {
        l = NULL;
        r = NULL;
        y = NULL;
    }
};
struct nodeY
{
    long long v = 0;
    nodeY* l;
    nodeY* r;
    nodeY()
    {
        l = NULL;
        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 - 1;
    maxC = C - 1;
    root = new nodeX();
}
void updateY(nodeY* p, nodeY* l, nodeY* r, 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)
    {
        if (l == NULL && r == NULL)
            p->v = K;
        else if (l == NULL)
            p->v = r->v;
        else if (r == NULL)
            p->v = l->v;
        else
            p->v = gcd2(l->v, r->v);
        return;
    }
    int m = (sY + eY)/2;
    if (Q <= m)
    {
        if (p->l == NULL)
            p->l = new nodeY();
        updateY(p->l, (l == NULL)?NULL:l->l, (r == NULL)?NULL:r->l, Q, K, sY, m);
    }
    else
    {
        if (p->r == NULL)
            p->r = new nodeY();
        updateY(p->r, (l == NULL)?NULL:l->r, (r == NULL)?NULL:r->r, Q, K, m + 1, eY);
    }
    if (p->l == NULL && p->r == NULL)
        while (1);
    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);
    // printf("sY %d eY %d %d\n", sY, eY, p->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, NULL, NULL, 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, (p->l == NULL)?NULL:p->l->y, (p->r == NULL)?NULL:p->r->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)
    {
        if (p->l != NULL)
            r = gcd2(r, queryY(p->l, qsY, min(qeY, m), sY, m));
    }
    if (qeY >= m + 1)
    {
        if (p->r != NULL)
            r = gcd2(r, queryY(p->r, max(qsY, m + 1), qeY, m + 1, eY));
    }
    // printf("%lld\n", r);
    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)
    {
        if (p->y == NULL)
            return 0;
        return queryY(p->y, qsY, qeY, 0, maxC);
    }
    int m = (sX + eX)/2;
    long long r = 0;
    if (qsX <= m)
    {
        if (p->l != NULL)
            r = gcd2(r, queryX(p->l, qsX, min(qeX, m), qsY, qeY, sX, m));
    }
    if (qeX >= m + 1)
    {
        if (p->r != NULL)
            r = gcd2(r, queryX(p->r, max(qsX, m + 1), qeX, qsY, qeY, m + 1, eX));
    }
    // printf("%d %d %lld\n", sX, eX, r);
    return r;
}
long long calculate(int P, int Q, int U, int V)
{
    return queryX(root, P, U, Q, V, 0, maxR);
}

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 2 ms 584 KB Output is correct
6 Correct 2 ms 624 KB Output is correct
7 Correct 2 ms 624 KB Output is correct
8 Correct 2 ms 624 KB Output is correct
9 Correct 2 ms 764 KB Output is correct
10 Correct 2 ms 764 KB Output is correct
11 Correct 2 ms 880 KB Output is correct
12 Correct 2 ms 880 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 880 KB Output is correct
2 Correct 2 ms 880 KB Output is correct
3 Correct 2 ms 880 KB Output is correct
4 Correct 755 ms 17668 KB Output is correct
5 Correct 458 ms 21744 KB Output is correct
6 Correct 722 ms 23284 KB Output is correct
7 Correct 815 ms 27776 KB Output is correct
8 Correct 599 ms 28988 KB Output is correct
9 Correct 837 ms 36764 KB Output is correct
10 Correct 714 ms 41164 KB Output is correct
11 Correct 2 ms 41164 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 41164 KB Output is correct
2 Correct 3 ms 41164 KB Output is correct
3 Correct 3 ms 41164 KB Output is correct
4 Correct 2 ms 41164 KB Output is correct
5 Correct 2 ms 41164 KB Output is correct
6 Correct 3 ms 41164 KB Output is correct
7 Correct 3 ms 41164 KB Output is correct
8 Correct 2 ms 41164 KB Output is correct
9 Correct 2 ms 41164 KB Output is correct
10 Correct 2 ms 41164 KB Output is correct
11 Correct 2 ms 41164 KB Output is correct
12 Correct 1095 ms 51600 KB Output is correct
13 Correct 2736 ms 51600 KB Output is correct
14 Correct 375 ms 51600 KB Output is correct
15 Correct 3417 ms 57768 KB Output is correct
16 Correct 437 ms 71356 KB Output is correct
17 Correct 1415 ms 71356 KB Output is correct
18 Correct 2543 ms 81916 KB Output is correct
19 Correct 2286 ms 87264 KB Output is correct
20 Correct 2036 ms 91996 KB Output is correct
21 Correct 2 ms 91996 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 91996 KB Output is correct
2 Correct 2 ms 91996 KB Output is correct
3 Correct 2 ms 91996 KB Output is correct
4 Correct 2 ms 91996 KB Output is correct
5 Correct 2 ms 91996 KB Output is correct
6 Correct 2 ms 91996 KB Output is correct
7 Correct 2 ms 91996 KB Output is correct
8 Correct 2 ms 91996 KB Output is correct
9 Correct 2 ms 91996 KB Output is correct
10 Correct 2 ms 91996 KB Output is correct
11 Correct 2 ms 91996 KB Output is correct
12 Correct 777 ms 91996 KB Output is correct
13 Correct 483 ms 95252 KB Output is correct
14 Correct 1033 ms 96836 KB Output is correct
15 Correct 892 ms 101288 KB Output is correct
16 Correct 553 ms 102468 KB Output is correct
17 Correct 921 ms 110172 KB Output is correct
18 Correct 764 ms 114444 KB Output is correct
19 Correct 1168 ms 125064 KB Output is correct
20 Correct 2675 ms 125064 KB Output is correct
21 Correct 378 ms 125064 KB Output is correct
22 Correct 3227 ms 131200 KB Output is correct
23 Correct 301 ms 144800 KB Output is correct
24 Correct 1344 ms 144800 KB Output is correct
25 Correct 2430 ms 155348 KB Output is correct
26 Correct 2201 ms 160852 KB Output is correct
27 Correct 1851 ms 165428 KB Output is correct
28 Correct 1381 ms 256000 KB Output is correct
29 Execution timed out 13075 ms 256000 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256000 KB Output is correct
2 Correct 3 ms 256000 KB Output is correct
3 Correct 2 ms 256000 KB Output is correct
4 Correct 2 ms 256000 KB Output is correct
5 Correct 2 ms 256000 KB Output is correct
6 Correct 2 ms 256000 KB Output is correct
7 Correct 2 ms 256000 KB Output is correct
8 Correct 2 ms 256000 KB Output is correct
9 Correct 3 ms 256000 KB Output is correct
10 Correct 2 ms 256000 KB Output is correct
11 Correct 2 ms 256000 KB Output is correct
12 Correct 751 ms 256000 KB Output is correct
13 Correct 480 ms 256000 KB Output is correct
14 Correct 778 ms 256000 KB Output is correct
15 Correct 889 ms 256000 KB Output is correct
16 Correct 529 ms 256000 KB Output is correct
17 Correct 899 ms 256000 KB Output is correct
18 Correct 813 ms 256000 KB Output is correct
19 Correct 1135 ms 256000 KB Output is correct
20 Correct 2754 ms 256000 KB Output is correct
21 Correct 387 ms 256000 KB Output is correct
22 Correct 3205 ms 256000 KB Output is correct
23 Correct 331 ms 256000 KB Output is correct
24 Correct 1383 ms 256000 KB Output is correct
25 Correct 2575 ms 256000 KB Output is correct
26 Correct 2075 ms 256000 KB Output is correct
27 Correct 1877 ms 256000 KB Output is correct
28 Correct 1401 ms 256000 KB Output is correct
29 Execution timed out 13091 ms 256000 KB Time limit exceeded
30 Halted 0 ms 0 KB -