oj.uz

Submission #253578

# Submission time Handle Problem Language Result Execution time Memory
253578 2020-07-28T10:56:01 Z test2 Game (IOI13_game) C++14
63 / 100
 2541 ms 172024 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(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 1 ms 896 KB Output is correct
2 Correct 6 ms 1924 KB Output is correct
3 Correct 3 ms 1920 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 5 ms 1920 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 3 ms 1664 KB Output is correct
10 Correct 2 ms 896 KB Output is correct
11 Correct 2 ms 1152 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1000 ms 167384 KB Output is correct
5 Correct 839 ms 171720 KB Output is correct
6 Correct 1040 ms 169464 KB Output is correct
7 Correct 1041 ms 169212 KB Output is correct
8 Correct 669 ms 88012 KB Output is correct
9 Correct 1056 ms 169348 KB Output is correct
10 Correct 991 ms 168904 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 3 ms 1920 KB Output is correct
3 Correct 3 ms 1920 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 3 ms 1920 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 3 ms 1664 KB Output is correct
10 Correct 2 ms 1024 KB Output is correct
11 Correct 2 ms 1152 KB Output is correct
12 Correct 1546 ms 148856 KB Output is correct
13 Correct 2060 ms 139196 KB Output is correct
14 Correct 642 ms 132600 KB Output is correct
15 Correct 2337 ms 146876 KB Output is correct
16 Correct 808 ms 156408 KB Output is correct
17 Correct 1446 ms 81288 KB Output is correct
18 Correct 2468 ms 157688 KB Output is correct
19 Correct 2137 ms 158072 KB Output is correct
20 Correct 2013 ms 157440 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 3 ms 1920 KB Output is correct
3 Correct 3 ms 1920 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 3 ms 1920 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 5 ms 1664 KB Output is correct
10 Correct 1 ms 896 KB Output is correct
11 Correct 2 ms 1152 KB Output is correct
12 Correct 1020 ms 167416 KB Output is correct
13 Correct 793 ms 172024 KB Output is correct
14 Correct 1031 ms 169592 KB Output is correct
15 Correct 1030 ms 169336 KB Output is correct
16 Correct 683 ms 87928 KB Output is correct
17 Correct 1056 ms 169460 KB Output is correct
18 Correct 1014 ms 168952 KB Output is correct
19 Correct 1547 ms 152720 KB Output is correct
20 Correct 2043 ms 143044 KB Output is correct
21 Correct 677 ms 137336 KB Output is correct
22 Correct 2253 ms 147064 KB Output is correct
23 Correct 792 ms 156536 KB Output is correct
24 Correct 1464 ms 81400 KB Output is correct
25 Correct 2464 ms 157736 KB Output is correct
26 Correct 2088 ms 158200 KB Output is correct
27 Correct 2019 ms 157264 KB Output is correct
28 Incorrect 410 ms 142968 KB Output isn't correct
29 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 Correct 3 ms 1920 KB Output is correct
3 Correct 4 ms 1920 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 3 ms 1920 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 3 ms 1664 KB Output is correct
10 Correct 1 ms 896 KB Output is correct
11 Correct 2 ms 1152 KB Output is correct
12 Correct 1004 ms 167396 KB Output is correct
13 Correct 867 ms 171640 KB Output is correct
14 Correct 1084 ms 169476 KB Output is correct
15 Correct 1105 ms 169364 KB Output is correct
16 Correct 686 ms 87960 KB Output is correct
17 Correct 1097 ms 169320 KB Output is correct
18 Correct 1018 ms 169056 KB Output is correct
19 Correct 1560 ms 152952 KB Output is correct
20 Correct 2076 ms 143032 KB Output is correct
21 Correct 650 ms 137336 KB Output is correct
22 Correct 2220 ms 146960 KB Output is correct
23 Correct 806 ms 156304 KB Output is correct
24 Correct 1416 ms 81340 KB Output is correct
25 Correct 2541 ms 157792 KB Output is correct
26 Correct 2118 ms 157932 KB Output is correct
27 Correct 2013 ms 157392 KB Output is correct
28 Incorrect 413 ms 142968 KB Output isn't correct
29 Halted 0 ms 0 KB -