Submission #253580

#	Time	Username	Problem	Language	Result	Execution time	Memory
253580		test2	Game (IOI13_game)	C++14	10 / 100	1848 ms	256004 KiB

game

#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 (stderr)

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