oj.uz

Submission #432412

# Submission time Handle Problem Language Result Execution time Memory
432412 2021-06-18T09:20:32 Z p_square Game (IOI13_game) C++14
37 / 100
 13000 ms 14636 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll r, c;
vector <ll> lqry;

struct node
{
    ll val, North, South, West, East;
    node *NE, *NW, *SE, *SW;
    node(ll a, ll b, ll c, ll d)
    {
        North = a, South = b, West = c, East = d;
        val = 0;
    }
    node() {}
};

node *last = new node(-1, -1, -1, -1);

void lastify(node *th)
{
    th->NE = last;
    th->NW = last;
    th->SE = last;
    th->SW = last;
}

node *rt = new node();

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;
}

ll mgcd(ll a, ll b, ll c, ll d)
{
    a = gcd2(a, b);
    a = gcd2(a, c);
    a = gcd2(a, d);
    return a;
}

void update_seg(node* cur, ll row, ll col, ll val)
{
    //cout<<cur->North<<" "<<cur->South<<" "<<cur->West<<" "<<cur->East<<endl;
    if(cur -> North > row || cur -> South < row)
        return;

    if(cur -> West > col || cur -> East < col)
        return;

    if(cur -> North == cur -> South && cur -> East == cur -> West)
    {
        cur->val = val;
        return;
    }

    ll mrow = (cur -> North + cur -> South)/2;
    ll mcol = (cur -> East + cur -> West)/2;

    if(row <= mrow && col <= mcol)
    {
        if(cur -> NW == last)
        {
            cur -> NW = new node(cur->North, mrow, cur -> West, mcol);
            lastify(cur->NW);
        }
        update_seg(cur->NW, row, col, val);
    }

    if(row <= mrow && col > mcol)
    {
        if(cur -> NE == last)
        {
            cur -> NE = new node(cur->North, mrow, mcol+1, cur->East);
            lastify(cur->NE);
        }
        update_seg(cur->NE, row, col, val);
    }

    if(row > mrow && col <= mcol)
    {
        if(cur -> SW == last)
        {
            cur -> SW = new node(mrow+1, cur->South, cur -> West, mcol);
            lastify(cur->SW);
        }
        update_seg(cur->SW, row, col, val);
    }

    if(row > mrow && col > mcol)
    {
        if(cur -> SE == last)
        {
            cur -> SE = new node(mrow+1, cur->South, mcol+1, cur->East);
            lastify(cur->SE);
        }
        update_seg(cur->SE, row, col, val);
    }

    cur->val = mgcd((cur->NE)->val, (cur->NW)->val, (cur->SE)->val, (cur->SW)->val);
    //cout<<cur->North<<" "<<cur->South<<" "<<cur->West<<" "<<cur->East<<" "<<cur->val<<endl;
}

void query_seg(node *cur, ll top, ll bottom, ll left, ll right)
{
    if(cur->North > bottom || cur -> South < top)
        return;

    if(cur -> East < left || cur -> West > right)
        return;

    if(cur->East <= right && cur->West >= left && cur->North >= top && cur->South <= bottom)
    {
        lqry.push_back(cur->val);
        return;
    }

    query_seg(cur->NE, top, bottom, left, right);
    query_seg(cur->NW, top, bottom, left, right);
    query_seg(cur->SE, top, bottom, left, right);
    query_seg(cur->SW, top, bottom, left, right);
}

void init(int R, int C) {
    /* ... */
    r = R;
    c = C;
    rt -> North = 0;
    rt -> South = r-1;
    rt -> West = 0;
    rt -> East = c-1;
    lastify(rt);
}

void update(int P, int Q, long long K) {
    update_seg(rt, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    lqry.clear();
    lqry.push_back(0);
    query_seg(rt, P, U, Q, V);
    sort(lqry.begin(), lqry.end());

    ll ind = 0;
    for(int i = 0; i<int(lqry.size()); i++)
    {
        if(lqry[i] != 0)
        {
            ind = i;
            for(int j = i; j<int(lqry.size()); j++)
            {
                lqry[i] = gcd2(lqry[i], lqry[j]);
            }
            break;
        }
    }
    return lqry[ind];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1427 ms 14636 KB Output is correct
5 Correct 1020 ms 14468 KB Output is correct
6 Correct 803 ms 12024 KB Output is correct
7 Correct 1006 ms 11780 KB Output is correct
8 Correct 537 ms 9480 KB Output is correct
9 Correct 920 ms 11868 KB Output is correct
10 Correct 871 ms 11532 KB Output is correct
11 Correct 0 ms 204 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 7248 ms 11716 KB Output is correct
13 Execution timed out 13064 ms 4264 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 292 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1449 ms 14632 KB Output is correct
13 Correct 1048 ms 14460 KB Output is correct
14 Correct 881 ms 12008 KB Output is correct
15 Correct 1016 ms 11972 KB Output is correct
16 Correct 533 ms 9540 KB Output is correct
17 Correct 944 ms 11956 KB Output is correct
18 Correct 847 ms 11544 KB Output is correct
19 Correct 7401 ms 11716 KB Output is correct
20 Execution timed out 13039 ms 4132 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1446 ms 14528 KB Output is correct
13 Correct 1049 ms 14404 KB Output is correct
14 Correct 829 ms 12072 KB Output is correct
15 Correct 1104 ms 11800 KB Output is correct
16 Correct 572 ms 9444 KB Output is correct
17 Correct 948 ms 11872 KB Output is correct
18 Correct 886 ms 11472 KB Output is correct
19 Correct 7436 ms 11680 KB Output is correct
20 Execution timed out 13095 ms 4088 KB Time limit exceeded
21 Halted 0 ms 0 KB -