oj.uz

Submission #57539

# Submission time Handle Problem Language Result Execution time Memory
57539 2018-07-15T08:20:15 Z Crown Game (IOI13_game) C++14
100 / 100
 6168 ms 232448 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;

const int maxr = 1e9+5;
const int maxc = 1e9+5; 

long long gcd2(long long X, long long Y)
{
    if(X == 0 || Y == 0)
    {
        return X+Y;
    }
    long long tmp;
    while(X != Y && Y != 0)
    {
        tmp = X;
        X = Y;
        Y = tmp%Y;
    }
    return X;
}

struct layer2_node
{
    layer2_node(int low, int high) : low(low), high(high), left(NULL), right(NULL), value(0LL) {}
    int low, high;
    layer2_node *left;
    layer2_node *right;
    ll value;   
};

struct layer1_node
{
    layer1_node() : left(NULL), right(NULL), l2(0, maxc) {} 
    layer1_node *left, *right;
    layer2_node l2;
};

static layer1_node root;

static void update2(layer2_node* node, int Q, long long K)
{
    int low = node->low;
    int high = node->high;
    int mid = (low+high)/2;
    if(low == high)
    {
        node->value = K;
        return;
    }

    layer2_node*& tgt = Q<=mid ? node->left : node->right;

    if(tgt == NULL)
    {
        tgt = new layer2_node(Q, Q);
        tgt->value = K;
    }
    else if(tgt->low <= Q && Q<= tgt->high)
    {
        update2(tgt, Q, K);
    }
    else
    {
        do
        {
            if(Q<= mid) high = mid;
            else low = mid+1;
            mid = (low+high)/2;
        }
        while((Q<= mid) == (tgt->low <= mid));

        layer2_node* newnode = new layer2_node(low, high);
        (tgt->low<= mid? newnode->left : newnode->right) = tgt;
        tgt = newnode;

        update2(newnode, Q, K);
    }
    node->value = gcd2(node->left? node->left->value: 0, node->right?node->right->value:0);
}

ll query2(layer2_node *nd, int A, int B)
{
    if(nd == NULL || B< nd->low || A> nd->high) return 0;
    else if(A<= nd->low && nd->high <= B) return nd->value;
    return gcd2(query2(nd->left, A, B), query2(nd->right, A, B));
}

static void update1(layer1_node *node, int low, int high, int P, int Q, ll K)
{
    int mid = (low+high)/2;
    if(low == high)
    {
        update2(&node->l2, Q, K);
    }
    else
    {
        layer1_node*& newnode = P<= mid? node->left : node->right;
        if(P<= mid) high = mid;
        else low = mid+1;
        if(newnode == NULL)
        {
            newnode = new layer1_node();
        }
        update1(newnode, low, high, P, Q, K);
        K = gcd2(node->left?query2(&node->left->l2, Q, Q) : 0, node->right?query2(&node->right->l2, Q, Q) : 0);
        update2(&node->l2, Q, K);
    }
}

ll query1(layer1_node* nd, int low, int high, int A1, int B1, int A2, int B2)
{
    if(nd == NULL || B1< low || high < A1)
    {
        return 0;
    }
    else if(A1<= low && high<= B1)
    {
        return query2(&nd->l2, A2, B2);
    }
    int mid = (low+high)/2;
    return gcd2(query1(nd->left, low, mid, A1, B1, A2, B2), query1(nd->right, mid+1, high, A1, B1, A2, B2));    
}
void init(int R, int C){}
void update(int P, int Q, long long K)
{
    update1(&root, 0, maxr, P, Q, K);
}

long long calculate(int P, int Q, int U, int V)
{
    return query1(&root, 0, maxr, 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;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 6 ms 732 KB Output is correct
3 Correct 5 ms 784 KB Output is correct
4 Correct 3 ms 784 KB Output is correct
5 Correct 3 ms 784 KB Output is correct
6 Correct 5 ms 784 KB Output is correct
7 Correct 3 ms 784 KB Output is correct
8 Correct 3 ms 784 KB Output is correct
9 Correct 4 ms 816 KB Output is correct
10 Correct 4 ms 816 KB Output is correct
11 Correct 4 ms 816 KB Output is correct
12 Correct 2 ms 816 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 816 KB Output is correct
2 Correct 3 ms 816 KB Output is correct
3 Correct 2 ms 816 KB Output is correct
4 Correct 1207 ms 35768 KB Output is correct
5 Correct 795 ms 36124 KB Output is correct
6 Correct 1553 ms 36124 KB Output is correct
7 Correct 1762 ms 36124 KB Output is correct
8 Correct 897 ms 36124 KB Output is correct
9 Correct 1736 ms 36124 KB Output is correct
10 Correct 1446 ms 36124 KB Output is correct
11 Correct 2 ms 36124 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 36124 KB Output is correct
2 Correct 5 ms 36124 KB Output is correct
3 Correct 6 ms 36124 KB Output is correct
4 Correct 2 ms 36124 KB Output is correct
5 Correct 3 ms 36124 KB Output is correct
6 Correct 6 ms 36124 KB Output is correct
7 Correct 4 ms 36124 KB Output is correct
8 Correct 2 ms 36124 KB Output is correct
9 Correct 4 ms 36124 KB Output is correct
10 Correct 3 ms 36124 KB Output is correct
11 Correct 3 ms 36124 KB Output is correct
12 Correct 1364 ms 36124 KB Output is correct
13 Correct 2844 ms 36124 KB Output is correct
14 Correct 518 ms 36124 KB Output is correct
15 Correct 3046 ms 36124 KB Output is correct
16 Correct 601 ms 36124 KB Output is correct
17 Correct 1800 ms 36124 KB Output is correct
18 Correct 3455 ms 36124 KB Output is correct
19 Correct 2768 ms 36124 KB Output is correct
20 Correct 2314 ms 36124 KB Output is correct
21 Correct 2 ms 36124 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 36124 KB Output is correct
2 Correct 5 ms 36124 KB Output is correct
3 Correct 4 ms 36124 KB Output is correct
4 Correct 3 ms 36124 KB Output is correct
5 Correct 3 ms 36124 KB Output is correct
6 Correct 5 ms 36124 KB Output is correct
7 Correct 3 ms 36124 KB Output is correct
8 Correct 3 ms 36124 KB Output is correct
9 Correct 4 ms 36124 KB Output is correct
10 Correct 3 ms 36124 KB Output is correct
11 Correct 3 ms 36124 KB Output is correct
12 Correct 1081 ms 36124 KB Output is correct
13 Correct 1012 ms 36124 KB Output is correct
14 Correct 1558 ms 36124 KB Output is correct
15 Correct 1708 ms 36124 KB Output is correct
16 Correct 974 ms 36124 KB Output is correct
17 Correct 1593 ms 36124 KB Output is correct
18 Correct 1374 ms 36124 KB Output is correct
19 Correct 1297 ms 36124 KB Output is correct
20 Correct 2591 ms 36124 KB Output is correct
21 Correct 484 ms 36124 KB Output is correct
22 Correct 3001 ms 36124 KB Output is correct
23 Correct 675 ms 36124 KB Output is correct
24 Correct 1605 ms 36124 KB Output is correct
25 Correct 3281 ms 36124 KB Output is correct
26 Correct 2569 ms 36124 KB Output is correct
27 Correct 2347 ms 36124 KB Output is correct
28 Correct 853 ms 36464 KB Output is correct
29 Correct 2228 ms 39008 KB Output is correct
30 Correct 4449 ms 39008 KB Output is correct
31 Correct 4359 ms 39008 KB Output is correct
32 Correct 566 ms 39008 KB Output is correct
33 Correct 878 ms 39008 KB Output is correct
34 Correct 1337 ms 39008 KB Output is correct
35 Correct 1832 ms 39008 KB Output is correct
36 Correct 4070 ms 39008 KB Output is correct
37 Correct 3192 ms 47172 KB Output is correct
38 Correct 2768 ms 57232 KB Output is correct
39 Correct 2662 ms 60556 KB Output is correct
40 Correct 3 ms 60556 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 60556 KB Output is correct
2 Correct 5 ms 60556 KB Output is correct
3 Correct 7 ms 60556 KB Output is correct
4 Correct 3 ms 60556 KB Output is correct
5 Correct 3 ms 60556 KB Output is correct
6 Correct 6 ms 60556 KB Output is correct
7 Correct 2 ms 60556 KB Output is correct
8 Correct 3 ms 60556 KB Output is correct
9 Correct 3 ms 60556 KB Output is correct
10 Correct 4 ms 60556 KB Output is correct
11 Correct 4 ms 60556 KB Output is correct
12 Correct 1272 ms 71584 KB Output is correct
13 Correct 863 ms 75732 KB Output is correct
14 Correct 1433 ms 77500 KB Output is correct
15 Correct 1478 ms 81736 KB Output is correct
16 Correct 1107 ms 81736 KB Output is correct
17 Correct 1965 ms 90820 KB Output is correct
18 Correct 1441 ms 95352 KB Output is correct
19 Correct 1550 ms 95352 KB Output is correct
20 Correct 2727 ms 95352 KB Output is correct
21 Correct 575 ms 95352 KB Output is correct
22 Correct 2957 ms 95352 KB Output is correct
23 Correct 678 ms 95352 KB Output is correct
24 Correct 1667 ms 95352 KB Output is correct
25 Correct 2951 ms 95352 KB Output is correct
26 Correct 2867 ms 95352 KB Output is correct
27 Correct 2150 ms 95352 KB Output is correct
28 Correct 923 ms 109720 KB Output is correct
29 Correct 1946 ms 112456 KB Output is correct
30 Correct 4948 ms 112456 KB Output is correct
31 Correct 4169 ms 112456 KB Output is correct
32 Correct 516 ms 112456 KB Output is correct
33 Correct 886 ms 112456 KB Output is correct
34 Correct 1322 ms 112456 KB Output is correct
35 Correct 2007 ms 112456 KB Output is correct
36 Correct 3872 ms 112456 KB Output is correct
37 Correct 3071 ms 112456 KB Output is correct
38 Correct 3203 ms 112456 KB Output is correct
39 Correct 967 ms 147548 KB Output is correct
40 Correct 3313 ms 159260 KB Output is correct
41 Correct 6168 ms 159260 KB Output is correct
42 Correct 5937 ms 159260 KB Output is correct
43 Correct 1931 ms 179576 KB Output is correct
44 Correct 626 ms 179576 KB Output is correct
45 Correct 2518 ms 179576 KB Output is correct
46 Correct 5012 ms 210736 KB Output is correct
47 Correct 5105 ms 221656 KB Output is correct
48 Correct 4497 ms 232448 KB Output is correct
49 Correct 3 ms 232448 KB Output is correct