oj.uz

답안 #253577

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
253577 2020-07-28T10:54:57 Z test2 게임 (IOI13_game) C++14
10 / 100
 1510 ms 54496 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1 << 10;

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 0 ms 384 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Incorrect 256 ms 40184 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 988 ms 54496 KB Output is correct
13 Correct 1510 ms 44712 KB Output is correct
14 Incorrect 303 ms 40056 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 704 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Incorrect 261 ms 40312 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 768 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Incorrect 260 ms 40312 KB Output isn't correct
13 Halted 0 ms 0 KB -