oj.uz

Submission #962903

# Submission time Handle Problem Language Result Execution time Memory
962903 2024-04-14T09:32:51 Z NValchanov Game (IOI13_game) C++17
63 / 100
 1249 ms 256000 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;
typedef long long ll;

const ll MAXN = 2e3 + 10;

long long gcd2(long long X, long long Y) {

    if(X == 0 && Y == 0)
        return 0;
    else if(X == 0 && Y != 0)
        return Y;
    else if(X != 0 && Y == 0)
        return X;

    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

ll n,m;

/// 2D SEGMENT TREE CODE

struct segment_tree_2d
{
    /// SEGMENT TREE CODE
    struct segment_tree
    {
        /// NODE CODE
        struct node
        {
            node *l;
            node *r;
            ll val;
            node()
            {
                val = 0;
                l = nullptr;
                r = nullptr;
            }
            node(ll _val)
            {
                val = _val;
                l = nullptr;
                r = nullptr;
            }
        };


        node *root;
        segment_tree *l;
        segment_tree *r;

        segment_tree()
        {
            root = new node();
            l = nullptr;
            r = nullptr;
        }

        void merge_nodes(node *tree)
        {
            if(tree -> l == nullptr)
                tree -> l = new node();
            if(tree -> r == nullptr)
                tree -> r = new node();
            tree -> val = gcd2(tree -> l -> val, tree -> r -> val);
        }

        void update(node *tree, ll left, ll right, ll pos, ll x)
        {
            if(left == right)
            {
                tree -> val = x;
                return;
            }

            ll mid = left + (right - left) / 2;

            if(pos <= mid)
            {
                if(tree -> l == nullptr)
                    tree -> l = new node();
                update(tree -> l, left, mid, pos, x);
            }
            else
            {
                if(tree -> r == nullptr)
                    tree -> r = new node();
                update(tree -> r, mid + 1, right, pos, x);
            }

            merge_nodes(tree);
        }

        ll query(node *tree, ll left, ll right, ll qleft, ll qright)
        {
            if(tree == nullptr)
                return 0LL;

            if(qright < left || right < qleft)
                return 0LL;

            if(qleft <= left && right <= qright)
                return tree -> val;

            ll mid = left + (right - left) / 2;

            ll Lnode = query(tree -> l, left, mid, qleft, qright);
            ll Rnode = query(tree -> r, mid + 1, right, qleft, qright);

            return gcd2(Lnode, Rnode);
        }

        void update(ll pos, ll x)
        {
            update(root, 0, m - 1, pos, x);
        }

        ll query(ll qleft, ll qright)
        {
            return query(root, 0, m - 1, qleft, qright);
        }
    };

    segment_tree *root;
    segment_tree_2d()
    {
        root = new segment_tree();
    }

    void merge(segment_tree *tree, ll pos)
    {
        if(tree -> l == nullptr)
            tree -> l = new segment_tree();
        if(tree -> r == nullptr)
            tree -> r = new segment_tree();

        ll Lnode = tree -> l -> query(pos, pos);
        ll Rnode = tree -> r -> query(pos, pos);

        tree -> update(pos, gcd2(Lnode, Rnode));
    }

    void update(segment_tree *tree, ll left, ll right, ll row, ll col, ll x)
    {
        if(left == right)
        {
            tree -> update(col, x);
            return;
        }

        ll mid = left + (right - left) / 2;

        if(row <= mid)
        {
            if(tree -> l == nullptr)
                tree -> l = new segment_tree();
            update(tree -> l, left, mid, row, col, x);
        }
        else
        {
            if(tree -> r == nullptr)
                tree -> r = new segment_tree();
            update(tree -> r, mid + 1, right, row, col, x);
        }

        merge(tree, col);
    }

    ll query(segment_tree *tree, ll left, ll right, ll qleft_row, ll qright_row, ll qleft_col, ll qright_col)
    {
        if(tree == nullptr)
            return 0LL;

        if(qright_row < left || right < qleft_row)
            return 0LL;

        if(qleft_row <= left && right <= qright_row)
            return tree -> query(qleft_col, qright_col);

        ll mid = left + (right - left) / 2;

        ll Lnode = query(tree -> l, left, mid, qleft_row, qright_row, qleft_col, qright_col);
        ll Rnode = query(tree -> r, mid + 1, right, qleft_row, qright_row, qleft_col, qright_col);

        return gcd2(Lnode, Rnode);
    }

    void update(ll row, ll col, ll x)
    {
        update(root, 0, n - 1, row, col, x);
    }

    ll query(ll qleft_row, ll qright_row, ll qleft_col, ll qright_col)
    {
        return query(root, 0, n - 1, qleft_row, qright_row, qleft_col, qright_col);
    }

};

segment_tree_2d s;

void init(int R, int C)
{
    n = R;
    m = C;
}

void update(int i, int j, long long k)
{
    s.update(i,j,k);
}

ll calculate(int i1, int j1, int i2, int j2)
{
    ll result = s.query(i1, i2, j1, j2);
    return result;
}
/**
int main()
{
    ll r,c,n;
    cin >> r >> c >> n;
    init(r,c);

    for(int i = 0; i < n; i++)
    {
        ll type;
        cin >> type;
        if(type == 1)
        {
            ll x,y,w;
            cin >> x >> y >> w;
            update(x,y,w);
        }
        else
        {
            ll i1,j1,i2,j2;
            cin >> i1 >> j1 >> i2 >> j2;

            cout << calculate(i1, j1, i2, j2) << endl;
        }
    }

    return 0;
}
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 412 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 458 ms 18280 KB Output is correct
5 Correct 303 ms 18508 KB Output is correct
6 Correct 407 ms 15672 KB Output is correct
7 Correct 470 ms 15848 KB Output is correct
8 Correct 299 ms 10496 KB Output is correct
9 Correct 421 ms 15640 KB Output is correct
10 Correct 408 ms 15088 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 716 ms 22544 KB Output is correct
13 Correct 1008 ms 8644 KB Output is correct
14 Correct 245 ms 1160 KB Output is correct
15 Correct 1187 ms 13044 KB Output is correct
16 Correct 200 ms 29476 KB Output is correct
17 Correct 673 ms 18168 KB Output is correct
18 Correct 1249 ms 30076 KB Output is correct
19 Correct 1036 ms 29896 KB Output is correct
20 Correct 954 ms 29348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 462 ms 18244 KB Output is correct
13 Correct 312 ms 18708 KB Output is correct
14 Correct 418 ms 15656 KB Output is correct
15 Correct 415 ms 15444 KB Output is correct
16 Correct 306 ms 10088 KB Output is correct
17 Correct 433 ms 15972 KB Output is correct
18 Correct 420 ms 15188 KB Output is correct
19 Correct 709 ms 22492 KB Output is correct
20 Correct 1016 ms 8952 KB Output is correct
21 Correct 240 ms 1084 KB Output is correct
22 Correct 1219 ms 13144 KB Output is correct
23 Correct 187 ms 29612 KB Output is correct
24 Correct 673 ms 18380 KB Output is correct
25 Correct 1214 ms 30256 KB Output is correct
26 Correct 1050 ms 29916 KB Output is correct
27 Correct 955 ms 29568 KB Output is correct
28 Runtime error 527 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 446 ms 18312 KB Output is correct
13 Correct 310 ms 18736 KB Output is correct
14 Correct 371 ms 15652 KB Output is correct
15 Correct 436 ms 15340 KB Output is correct
16 Correct 281 ms 10100 KB Output is correct
17 Correct 433 ms 15592 KB Output is correct
18 Correct 404 ms 15188 KB Output is correct
19 Correct 708 ms 22524 KB Output is correct
20 Correct 1012 ms 8852 KB Output is correct
21 Correct 234 ms 1108 KB Output is correct
22 Correct 1169 ms 13064 KB Output is correct
23 Correct 189 ms 29520 KB Output is correct
24 Correct 698 ms 18216 KB Output is correct
25 Correct 1233 ms 29960 KB Output is correct
26 Correct 976 ms 30044 KB Output is correct
27 Correct 1014 ms 29244 KB Output is correct
28 Runtime error 481 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -