oj.uz

Submission #253554

# Submission time Handle Problem Language Result Execution time Memory
253554 2020-07-28T09:13:33 Z test2 Game (IOI13_game) C++14
0 / 100
 3 ms 1920 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1 << 20;

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

long long f(long long x, long long y)
{
        return gcd2(x, y);
}

struct node
{

        long long sum = 0;

        node *l, *r;

        node(int _sum) : sum(_sum), l(nullptr), r(nullptr)
        {
        }

        node(node *_l, node *_r) : l(_l), r(_r), sum(0)
        {
                if (l)
                        sum = f(sum, l->sum);
                if (r)
                        sum = f(sum, r->sum);
        }
};

node *update(node *nod, int L, int R, int idx, long long val)
{

        if (L == R)
        {
                nod->sum = val ; 
                return nod;
        }

        int mid = (L + R) >> 1;

        if (idx <= mid)
        {
                if (nod->l == NULL)
                {
                        nod->l = new node(0);
                }
                return new node(update(nod->l, L, mid, idx, val), nod->r);
        }
        else
        {
                if (nod->r == NULL)
                {
                        nod->r = new node(0);
                }
                return new node(nod->l, update(nod->r, mid + 1, R, idx, val));
        }

        return new node(nod->l, nod->r);
}

long long query(node *nod, int L, int R, int l, int r)
{
        if (l > r || l > R || r < L || nod == NULL)
                return 0;
        if (L >= l && R <= r)
        {
                return nod->sum;
        }

        int mid = (L + R) >> 1;

        long long s1 = query(nod->l, L, mid, l, r);
        long long s2 = query(nod->r, mid + 1, R, l, r);

        return f(s1, s2);
}

struct node2
{

        node *sum = new node(0);

        node2 *l, *r;

        node2()
        {
        }

        node2(node2 *_l, node2 *_r) : l(_l), r(_r)
        {
        }
};

node2 *root = new node2();

void upd(node2 *nod, int L, int R, int x, int y, long long z)
{

        if (L == R)
        {
                nod->sum = update(nod->sum, 1, N, y, z);
                return;
        }

        int mid = (L + R) >> 1;

        if (x <= mid)
        {
                if (nod->l == NULL)
                {
                        nod->l = new node2();
                }
                upd(nod->l, L, mid, x, y, z);
        }
        else
        {
                if (nod->r == NULL)
                {
                        nod->r = new node2();
                }
                upd(nod->r, mid + 1, R, x, y, z);
        }
        nod->sum = update(nod->sum, 1, N, y, z);
        return;
}

long long query2(node2 *nod, int L, int R, int l, int r, int x, int y)
{

        if (l > R || r < L || l > r || nod == NULL)
                return 0;

        if (L >= l && R <= r)
        {
                return query(nod->sum, 1, N, x, y);
        }

        int mid = (L + R) >> 1;

        long long s1 = query2(nod->l, L, mid, l, r, x, y);
        long long s2 = query2(nod->r, mid + 1, R, l, r, x, y);

        return f(s1, s2);
}

void init(int Q, int V)
{
}

void update(int P, int Q, long long K)
{
        P++;
        Q++;
        upd(root, 1, N, P, Q, K);
}

long long calculate(int P, int Q, int U, int V)
{
        P++;
        Q++;
        U++;
        V++;
        return query2(root, 1, N, 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;
      ^~~
game.cpp: In constructor 'node::node(node*, node*)':
game.cpp:30:19: warning: 'node::r' will be initialized after [-Wreorder]
         node *l, *r;
                   ^
game.cpp:28:25: warning:   'long long int node::sum' [-Wreorder]
         long long sum = 0;
                         ^
game.cpp:36:9: warning:   when initialized here [-Wreorder]
         node(node *_l, node *_r) : l(_l), r(_r), sum(0)
         ^~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Incorrect 1 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 1 ms 896 KB Output is correct
2 Incorrect 3 ms 1920 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 896 KB Output is correct
2 Incorrect 3 ms 1920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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