oj.uz

Submission #962990

# Submission time Handle Problem Language Result Execution time Memory
962990 2024-04-14T10:33:18 Z NValchanov Game (IOI13_game) C++17
63 / 100
 1386 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 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 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 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 496 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 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 461 ms 18236 KB Output is correct
5 Correct 334 ms 18512 KB Output is correct
6 Correct 420 ms 15612 KB Output is correct
7 Correct 444 ms 15276 KB Output is correct
8 Correct 289 ms 10144 KB Output is correct
9 Correct 488 ms 15444 KB Output is correct
10 Correct 461 ms 15116 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 0 ms 348 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 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 1 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 508 KB Output is correct
12 Correct 812 ms 22432 KB Output is correct
13 Correct 1086 ms 8740 KB Output is correct
14 Correct 275 ms 916 KB Output is correct
15 Correct 1223 ms 12900 KB Output is correct
16 Correct 204 ms 29520 KB Output is correct
17 Correct 776 ms 18336 KB Output is correct
18 Correct 1386 ms 29868 KB Output is correct
19 Correct 1181 ms 29868 KB Output is correct
20 Correct 1111 ms 29352 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 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 475 ms 18324 KB Output is correct
13 Correct 311 ms 18612 KB Output is correct
14 Correct 414 ms 15712 KB Output is correct
15 Correct 477 ms 15396 KB Output is correct
16 Correct 297 ms 10068 KB Output is correct
17 Correct 454 ms 15440 KB Output is correct
18 Correct 486 ms 15032 KB Output is correct
19 Correct 775 ms 22444 KB Output is correct
20 Correct 1100 ms 8776 KB Output is correct
21 Correct 259 ms 1104 KB Output is correct
22 Correct 1255 ms 13012 KB Output is correct
23 Correct 226 ms 29592 KB Output is correct
24 Correct 716 ms 18156 KB Output is correct
25 Correct 1384 ms 30048 KB Output is correct
26 Correct 1222 ms 30092 KB Output is correct
27 Correct 1082 ms 29412 KB Output is correct
28 Runtime error 529 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 0 ms 344 KB Output is correct
2 Correct 1 ms 604 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 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 424 KB Output is correct
12 Correct 490 ms 18404 KB Output is correct
13 Correct 311 ms 18512 KB Output is correct
14 Correct 395 ms 15716 KB Output is correct
15 Correct 469 ms 15572 KB Output is correct
16 Correct 288 ms 10160 KB Output is correct
17 Correct 460 ms 15608 KB Output is correct
18 Correct 402 ms 15184 KB Output is correct
19 Correct 745 ms 22472 KB Output is correct
20 Correct 1006 ms 8888 KB Output is correct
21 Correct 252 ms 896 KB Output is correct
22 Correct 1186 ms 13088 KB Output is correct
23 Correct 196 ms 29520 KB Output is correct
24 Correct 717 ms 18512 KB Output is correct
25 Correct 1303 ms 29776 KB Output is correct
26 Correct 1114 ms 29920 KB Output is correct
27 Correct 1081 ms 29296 KB Output is correct
28 Runtime error 525 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -