Submission #561395

#	Time	Username	Problem	Language	Result	Execution time	Memory
561395		stefantaga	Game (IOI13_game)	C++14	Compilation error	0 ms	0 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
struct TreapNode
{
    ll priority;
    ll val,g;
    int st,dr,poz;
    TreapNode *fiust,*fiudr;
    TreapNode (int poz,ll val)
    {
        priority = rng();
        val=val;
        st=dr=poz=poz;
        fiust=fiudr=NULL;
    }
    void update()
    {
        g=val;
        st=dr=poz;
        if (fiust)
        {
            g=__gcd(g,fiust->g);
            st=min(st,fiust->st);
            dr=max(dr,fiust->dr);
        }
        if (fiudr)
        {
            g=__gcd(g,fiudr->g);
            st=min(st,fiudr->st);
            dr=max(dr,fiudr->dr);
        }
    }
};

struct Treap
{
    TreapNode *root;
    Treap()
    {
        root = NULL;
    }
    void split(TreapNode *t,int poz,TreapNode *&st,TreapNode *&dr)
    {
        if (t==NULL)
        {
            return void(st=dr=NULL);
        }
        if (t->poz<poz)
        {
            split(t->fiudr,poz,t->fiudr,dr);
            st = t;
        }
        else
        {
            split(t->fiust,poz,st,t->fiust);
            dr=t;
        }
        t->update();
    }
    void Merge(TreapNode *&t,TreapNode *st,TreapNode *dr)
    {
        if (st==NULL||dr==NULL)
        {
            if (st==NULL)
            {
                t=dr;
            }
            else
            {
                t=st;
            }
            return;
        }
        if (st->priority<dr->priority)
        {
            Merge(st->fiudr,st->fiudr,dr);
            t=st;
        }
        else
        {
            Merge(dr->fiust,st,dr->fiust);
            t=dr;
        }
        t->update();
    }
    bool Find(int poz)
    {
        TreapNode *t = root;
        while (t)
        {
            if (t->poz==poz)
            {
                return true;
            }
            if (t->poz<poz)
            {
                t=t->fiudr;
            }
            else
            {
                t=t->fiust;
            }
        }
        return false;
    }
    void update(TreapNode *&t,int poz,ll val)
    {
        if (t->poz==poz)
        {
            t->val=val;
            t->update();
            return;
        }
        if (t->poz<poz)
        {
            update(t->fiudr,poz,val);
        }
        else
        {
            update(t->fiust,poz,val);
        }
        t->update();
    }
    void Insert(int poz,ll val)
    {
        if (Find(poz)==false)
        {
            TreapNode *T1,*T2;
            split(root,poz,T1,T2);
            Merge(root,T1,new TreapNode(poz,val));
            Merge(root,root,T2);
        }
        else
        {
            update(root,poz,val);
        }
    }
    ll query(TreapNode *t , int ua,int ub)
    {
        if (t==NULL)
        {
            return 0;
        }
        if (t->dr<ua||ub<t->dr)
        {
            return 0;
        }
        if (ua<=t->st&&t->dr<=ub)
        {
            return t->g;
        }
        return __gcd(query(t->fiust,ua,ub),query(t->fiudr,ua,ub));
    }
    ll query(int st,int dr)
    {
        if (root==NULL)
        {
            return 0;
        }
        return query(root,st,dr);
    }
};
struct SegTree
{
    int g;;
    int st;
    int dr;
    Treap *treap;
    SegTree *fiust,*fiudr;
    SegTree()
    {
        fiust=fiudr=nullptr;
    }
    SegTree(int lo,int hi)
    {
        fiust=fiudr=nullptr;
        st=lo;dr=hi;
    }
    void new_left()
    {
        if (fiust==nullptr)
        {
            fiust = new SegTree(st,(st+dr)/2);
        }
    }
    void new_right()
    {
        if (fiudr==nullptr)
        {
            fiudr = new SegTree((st+dr)/2+1,dr);
        }
    }
    void fix(int poz)
    {
        ll val=0;
        if (fiust)
        {
            val = __gcd(val,fiust->treap->query(poz,poz));
        }
        if (fiudr)
        {
            val = __gcd(val,fiudr->treap->query(poz,poz));
        }
        treap->Insert(poz,val);
    }
    void update(int x,int y,ll val)
    {
        if (dr<x||x<st)
        {
            return;
        }
        if (st==dr)
        {
            treap->Insert(y,val);
            return;
        }
        int mij = (st+dr)/2;
        if (x<=mij)
        {
            new_left();
            fiust->update(x,y,val);
        }
        else
        {
            new_right();
            fiudr->update(x,y,val);
        }
        fix(y);
    }
    ll query(int x,int x2,int y,int y2)
    {
        if (dr<x||x2<st)
        {
            return 0;
        }
        if (st<=x&&x2<=dr)
        {
            return treap->query(y,y2);
        }
        ll val = 0;
        if (fiust)
        {
           val = __gcd(val,fiust->query(x,x2,y,y2));
        }
        if (fiudr)
        {
            val = __gcd(val,fiudr->query(x,x2,y,y2));
        }
        return val;
    }
}*seg;
void Init(int n,int m)
{
    seg= new SegTree(1,n);
}
void update(int x,int y,ll k)
{
    seg->update(x+1,y+1,k);
}
long long calculate(int x,int y,int x2,int y2)
{
    return seg->query(x,x2,y,y2);
}

Compilation message (stderr)

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