oj.uz

Submission #253580

# Submission time Handle Problem Language Result Execution time Memory
253580 2020-07-28T11:00:38 Z test2 Game (IOI13_game) C++14
10 / 100
 1848 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1 << 30;

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(long long _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));
        }
}

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() : l(nullptr), r(nullptr)
        {
        }

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

node2 *root = new node2();

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 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;
        long long add = 0;
        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);
        }

        add = f( (nod -> l ? query(nod->l -> sum , 1 , N , y , y) : 0 )  ,
                 (nod -> r ? query(nod->r -> sum , 1 , N , y , y) : 0 )
                ) ; 

        nod->sum = update(nod->sum, 1, N, y, add );
        return;
}

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1664 KB Output is correct
2 Correct 6 ms 3584 KB Output is correct
3 Correct 11 ms 3584 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 6 ms 3584 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 5 ms 3200 KB Output is correct
10 Correct 4 ms 1408 KB Output is correct
11 Correct 4 ms 2048 KB Output is correct
12 Correct 1 ms 512 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1664 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Runtime error 1136 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1664 KB Output is correct
2 Correct 8 ms 3536 KB Output is correct
3 Correct 6 ms 3584 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 6 ms 3584 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 5 ms 3200 KB Output is correct
10 Correct 2 ms 1408 KB Output is correct
11 Correct 3 ms 2048 KB Output is correct
12 Runtime error 1848 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1664 KB Output is correct
2 Correct 6 ms 3584 KB Output is correct
3 Correct 6 ms 3584 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 6 ms 3584 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 5 ms 3200 KB Output is correct
10 Correct 2 ms 1408 KB Output is correct
11 Correct 3 ms 2048 KB Output is correct
12 Runtime error 1091 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1664 KB Output is correct
2 Correct 6 ms 3584 KB Output is correct
3 Correct 6 ms 3584 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 6 ms 3584 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 5 ms 3200 KB Output is correct
10 Correct 2 ms 1408 KB Output is correct
11 Correct 3 ms 2048 KB Output is correct
12 Runtime error 1140 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -