Submission #432374

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
432374	2021-06-18T08:43:34 Z	p_square	Game (IOI13_game)	C++14	Compilation error	0 ms	0 KB

game

#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(ll R, ll C) {
    /* ... */
    r = R;
    c = C;
    rt -> North = 0;
    rt -> South = r-1;
    rt -> West = 0;
    rt -> East = c-1;
    lastify(rt);
}

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

long long calculate(ll P, ll Q, ll U, ll V) {
    /* ... */
    return query_seg(rt, P, U, Q, V);
}

Compilation message

/usr/bin/ld: /tmp/ccppuDne.o: in function `main':
grader.c:(.text.startup+0x6b): undefined reference to `init'
/usr/bin/ld: grader.c:(.text.startup+0xd0): undefined reference to `calculate'
/usr/bin/ld: grader.c:(.text.startup+0x13e): undefined reference to `update'
collect2: error: ld returned 1 exit status