oj.uz

Submission #432376

# Submission time Handle Problem Language Result Execution time Memory
432376 2021-06-18T08:45:31 Z p_square Game (IOI13_game) C++14
37 / 100
 13000 ms 14632 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll r, c;

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

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

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

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

    ll a = query_seg(cur->NE, top, bottom, left, right);
    ll b = query_seg(cur->NW, top, bottom, left, right);
    ll c = query_seg(cur->SE, top, bottom, left, right);
    ll d = query_seg(cur->SW, top, bottom, left, right);
    return mgcd(a, b, c, d);
}

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) {
    /* ... */
    return query_seg(rt, P, U, Q, V);
}

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 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 288 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 1 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1202 ms 14600 KB Output is correct
5 Correct 802 ms 14448 KB Output is correct
6 Correct 870 ms 12060 KB Output is correct
7 Correct 1000 ms 11908 KB Output is correct
8 Correct 604 ms 9396 KB Output is correct
9 Correct 971 ms 11920 KB Output is correct
10 Correct 924 ms 11548 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 26.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 284 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 204 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 292 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 6453 ms 11640 KB Output is correct
13 Execution timed out 13011 ms 4604 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 216 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 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 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 1235 ms 14632 KB Output is correct
13 Correct 833 ms 14436 KB Output is correct
14 Correct 820 ms 12104 KB Output is correct
15 Correct 1006 ms 11976 KB Output is correct
16 Correct 582 ms 9380 KB Output is correct
17 Correct 958 ms 11956 KB Output is correct
18 Correct 873 ms 11632 KB Output is correct
19 Correct 6481 ms 11604 KB Output is correct
20 Execution timed out 13080 ms 4492 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 332 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 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 1213 ms 14520 KB Output is correct
13 Correct 790 ms 14348 KB Output is correct
14 Correct 842 ms 12076 KB Output is correct
15 Correct 1035 ms 11760 KB Output is correct
16 Correct 609 ms 9380 KB Output is correct
17 Correct 1006 ms 11940 KB Output is correct
18 Correct 919 ms 11596 KB Output is correct
19 Correct 6593 ms 11712 KB Output is correct
20 Execution timed out 13035 ms 4592 KB Time limit exceeded
21 Halted 0 ms 0 KB -