Submission #45222

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
45222	2018-04-11T22:10:09 Z	reality	Game (IOI13_game)	C++17	Compilation error	0 ms	0 KB

game

# include <bits/stdc++.h>
using namespace std;
# include <game.h>
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define db long double
# define pp pair < int , ll >
ll gcd(ll a,ll b)
{
    return !b ? a : gcd(b,a % b);
}
struct treap
{
    pp key;
    int pr;
    ll G = 0;
    treap *l,*r;
    void upd(void)
    {
        G = key.y;
        if (l) G = gcd(G,l->G);
        if (r) G = gcd(G,r->G);
    }
    treap(pp key,int pr,treap *l,treap *r) : key(key),pr(pr),l(l),r(r) {upd();}
    treap(pp key) : key(key),pr(rand()+1) {l = r = 0;upd();}
};
typedef treap * tp;
struct seg
{
    seg *l,*r;
    tp t;
    seg(seg *l,seg *r,tp t) : l(l),r(r),t(t) {}
    seg(void) : l(0),r(0),t(0) {}
};
void print(const tp Root)
{
    if (!Root) return;
    print(Root->l);
    cerr << Root->key.x << ' ' << Root->key.y << '\n';
    print(Root->r);
}
int Count = 0;
typedef seg * sg;
tp Merge(const tp a,const tp b)
{
    if (!a) return b;
    if (!b) return a;
    if (a->pr > b->pr) return new treap(a->key,a->pr,a->l,Merge(a->r,b));
    else return new treap(b->key,b->pr,Merge(a,b->l),b->r);
}
void split(const tp Root,pp K,tp &left,tp &right)
{
    left = right = 0;
    if (!Root) return;
    if (Root->key <= K)
    {
        split(Root->r,K,left,right);
        left = new treap(Root->key,Root->pr,Root->l,left);
    }
    else
    {
        split(Root->l,K,left,right);
        right = new treap(Root->key,Root->pr,right,Root->r);
    }
}
void add(tp &Root,pp Val)
{
    tp left,right;
    split(Root,Val,left,right);
    Root = Merge(Merge(left,new treap(Val)),right);
}
void del(tp &Root,pp Val)
{
    if (!Root) return;
    if (Root->key == Val) Root = Merge(Root->l,Root->r);
    else
    if (Root->key < Val) del(Root->r,Val);
    else del(Root->l,Val);
}
const ll inf = 1e18 + 5;
ll Get(const tp Root,int p,int u)
{
    tp left,mid,right;
    split(Root,{p-1,inf},left,mid);
    split(mid,{u,inf},left,right);
    return (!left ? 0 : left->G);
}
ll Acc(const tp Root,int pos)
{
    if (!Root) return -1;
    else
    if (Root->key.x == pos) return Root->key.y;
    else
    if (Root->key.x < pos) return Acc(Root->r,pos);
    else return Acc(Root->l,pos);
}
ll update(int p,int u,int pos1,int pos2,ll val,sg &Root)
{
    if (!Root) Root = new seg();
    if (p == u)
    {
        ll is = Acc(Root->t,pos2);
        if (is != -1) del(Root->t,{pos2,is});
        add(Root->t,{pos2,val});
        return is;
    }
    else
    {
        int m = (p + u) / 2;
        ll is = -1;
        if (pos1 <= m) is = update(p,m,pos1,pos2,val,Root->l);
        else is = update(m+1,u,pos1,pos2,val,Root->r);
        if (is != -1) del(Root->t,{pos2,is});
        add(Root->t,{pos2,val});
        return is;
    }
}
ll query(int p,int u,int l1,int r1,int l2,int r2,const sg Root)
{
    if (!Root) return 0;
    if (l1 <= p && u <= r1) return Get(Root->t,l2,r2);
    int m = (p + u) / 2;
    ll ans = 0;
    if (l1 <= m) ans = gcd(ans,query(p,m,l1,r1,l2,r2,Root->l));
    if (m+1<=r1) ans = gcd(ans,query(m+1,u,l1,r1,l2,r2,Root->r));
    return ans;
}
sg Root = 0;
int n,m;
void init(int a,int b)
{
    n = a;m = b;
}
void update(int l,int r,ll Val)
{
    update(1,n,l,r,val,Root);
}
ll calculate(int l1,int r1,int l2,int r2)
{
    return query(1,n,l1+1,l2+1,r1+1,r2+1,Root);
}

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 update(int, int, long long int)':
game.cpp:139:20: error: 'val' was not declared in this scope
     update(1,n,l,r,val,Root);
                    ^~~
game.cpp:139:20: note: suggested alternative: 'Val'
     update(1,n,l,r,val,Root);
                    ^~~
                    Val