Submission #98506

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
98506	2019-02-23T19:45:56 Z	luciocf	Game (IOI13_game)	C++14	Compilation error	0 ms	0 KB

game

// IOI 2013 - Game
// Lúcio Cardoso

#include <bits/stdc++.h>
#include "game.h"

using namespace std;

typedef long long ll;

int n, m;

struct Node {
    int w, ind;
    uint_fast64_t v, g;
    Node *l, *r;

    Node() {
        l = r = NULL;
        v = 0, g = 0, ind = -1;
        w = rand();
    }
};

typedef Node*& node_t;

struct Node2d {
    Node *f;
    Node2d *l, *r;

    Node2d() {
        f = NULL;
        l = r = NULL;
    }
};

Node2d *root = new Node2d;

ll gcd(ll X, ll Y) 
{
    uint_fast64_t tmp;
    while (X != Y && Y != 0) 
    {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

ll get(Node *t)
{
    if (!t) return 0;
    return t->g;
}

void operation(Node *t)
{
    if (!t) return;
    t->g = gcd( gcd(t->v, get(t->l)), get(t->r));
}

uint_fast64_t find(node_t t, int v, ll k)
{
    if (!t) return -1LL;

    if (t->ind == v)
    {
        if (k != -1) t->v = k, operation(t);
        return t->v;
    }
    else if (t->ind > v)
    {
        ll x = find(t->l, v, k);
        if (x != -1 && k != -1) operation(t);
        return x;
    }
    else
    {
        ll x = find(t->r, v, k);
        if (x != -1 && k != -1) operation(t);
        return x;
    }
}

void split(Node *t, node_t l, node_t r, int pos)
{
    if (!t) return void(l=r=NULL);

    if (pos < t->ind)
        split(t->l, l, t->l, pos), r = t;
    else
        split(t->r, t->r, r, pos), l = t;
    operation(t);
}

void merge(node_t t, Node *l, Node *r)
{
    if (l == NULL)
        t = r;
    else if (r == NULL)
        t = l;
    else if (l->w >= r->w)
        merge(l->r, l->r, r), t = l;
    else
        merge(r->l, l, r->l), t = r;
    operation(t);
}

void upd_y(node_t t, Node *left, Node *right, int pos, ll v)
{
    Node *tl = NULL, *tm = NULL, *tr = NULL;

    uint_fast64_t vl = find(left, pos, -1), vr = find(right, pos, -1);

    if (vl != -1) v = gcd(vl, v);
    if (vr != -1) v = gcd(vr, v);

    uint_fast64_t x = find(t, pos, v);

    if (x == -1)
    {
        Node *aux = new Node;
        aux->v = v, aux->ind = pos, aux->g = v;

        split(t, tl, tr, pos-1);
        merge(tl, tl, aux);
        merge(t, tl, tr);
    }
}

void upd_x(Node2d *nx, int lx, int rx, int x, int y, ll v)
{
    if (lx != rx)
    {
        int mx = (lx+rx)/2;
        if (x <= mx)
        {
            if (nx->l == NULL) nx->l = new Node2d;
            upd_x(nx->l, lx, mx, x, y, v);
        }
        else
        {
            if (nx->r == NULL) nx->r = new Node2d;
            upd_x(nx->r, mx+1, rx, x, y, v);
        }
    }
    upd_y(nx->f, (nx->l==NULL)?NULL:nx->l->f, (nx->r==NULL)?NULL:nx->r->f, y, v);
}

uint_fast64_t query_y(node_t t, int l, int r)
{
    if (!t) return 0;

    Node *tl = NULL, *tm = NULL, *tr = NULL;

    split(t, tl, tm, l-1);
    split(tm, t, tr, r);

    uint_fast64_t ans = 0;
    if (t) ans = t->g;
    merge(tm, tl, t);
    merge(t, tm, tr);
    return ans;
}

uint_fast64_t query_x(Node2d *nx, int tlx, int trx, int lx, int rx, int ly, int ry)
{
    if (nx == NULL || lx > rx) return 0;
    if (tlx == lx && trx == rx) return query_y(nx->f, ly, ry);

    int mx = (tlx+trx)/2;

    ll p1 = query_x(nx->l, tlx, mx, lx, min(rx, mx), ly, ry);
    ll p2 = query_x(nx->r, mx+1, trx, max(lx, mx+1), rx, ly, ry);

    return gcd(p1, p2);
}

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

void update(int P, int Q, long long K)
{
    upd_x(root, 0, n-1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V)
{
    return query_x(root, 0, n-1, P, U, Q, V);
}

int main(){}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
game.cpp: In function 'void upd_y(node_t, Node*, Node*, int, ll)':
game.cpp:117:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (vl != -1) v = gcd(vl, v);
         ~~~^~~~~
game.cpp:118:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (vr != -1) v = gcd(vr, v);
         ~~~^~~~~
game.cpp:122:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (x == -1)
         ~~^~~~~
game.cpp:113:23: warning: unused variable 'tm' [-Wunused-variable]
     Node *tl = NULL, *tm = NULL, *tr = NULL;
                       ^~
/tmp/ccHgHqie.o: In function `main':
game.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc90znRQ.o:grader.c:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status