Submission #962983

#	Time	Username	Problem	Language	Result	Execution time	Memory
962983		serkanrashid	Game (IOI13_game)	C++14	63 / 100	1357 ms	256000 KiB

game

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

using namespace std;

struct Tnode
{
    long long a;
    Tnode *l, *r;
    Tnode()
    {
        a = 0;
        l = r = nullptr;
    }
};

struct Tree
{
    Tnode *A;
    Tree *L, *R;
    Tree()
    {
        A = nullptr;
        L = R = nullptr;
    }
};

Tree *Root = nullptr;
int r,c;

int Ql,Qr,ql,qr,Pos,pos;
long long val;

long long gcd3(long long a, long long b)
{
    while(a&&b)
    {
        if(a>b) a %= b;
        else b %= a;
    }
    return a+b;
}

long long merge1(Tnode *&t1, Tnode *&t2)
{
    if(t1==nullptr&&t2==nullptr) return 0;
    if(t1==nullptr) return t2->a;
    if(t2==nullptr) return t1->a;
    return gcd3(t1->a,t2->a);
}

void upd(Tnode *&t, int l, int r)
{
    if(t==nullptr) t = new Tnode();
    if(l==r)
    {
        t->a = val;
        //cout << l << " " << r << " " << (t->a) << "upd" << endl;
        return;
    }
    int mid = (l+r)/2;
    if(pos<=mid) upd(t->l,l,mid+0);
    else upd(t->r,mid+1,r);
    t->a = merge1(t->l,t->r);
    //cout << l << " " << r << " " << (t->a) << "upd" << endl;
}

Tnode *getA(Tree *&t)
{
    if(t==nullptr) return nullptr;
    return t->A;
}

long long geta(Tnode *&t)
{
    if(t==nullptr) return 0;
    return (t->a);
}

void Merge(Tnode *&t, Tnode *t1, Tnode *t2, int l, int r)
{
    if(t==nullptr) t = new Tnode();
    if(l==r)
    {
        t->a = gcd3(geta(t1),geta(t2));
        //cout << l << " " << r << " " << (t->a) << "merge" << endl;
        return;
    }
    int mid = (l+r)/2;
    if(pos<=mid)
    {
        if(t1!=nullptr) t1 = t1->l;
        if(t2!=nullptr) t2 = t2->l;
        Merge(t->l,t1,t2,l,mid+0);
    }
    else
    {
        if(t1!=nullptr) t1 = t1->r;
        if(t2!=nullptr) t2 = t2->r;
        Merge(t->r,t1,t2,mid+1,r);
    }
    t->a = gcd3(geta(t->l),geta(t->r));
    //cout << l << " " << r << " " << (t->a) << "merge" << endl;
}

void Upd(Tree *&t, int l, int r)
{
    if(t==nullptr) t = new Tree();
    if(l==r)
    {
        upd(t->A,0,c-1);
        return;
    }
    int mid = (l+r)/2;
    if(Pos<=mid) Upd(t->L,l,mid+0);
    else Upd(t->R,mid+1,r);
    //cout << "new Merge" << " " << l << " " << r << endl;
    Merge(t->A,getA(t->L),getA(t->R),0,c-1);
}

void update(int P, int Q, long long K)
{
    Pos = P;
    pos = Q;
    val = K;
    Upd(Root,0,r-1);
    //cout << ((Root->A)->a) << "after update" << endl;
}

long long query(Tnode *t, int l, int r)
{
    if(r<ql||qr<l||l>r||t==nullptr) return 0;
    if(ql<=l&&r<=qr) return t->a;
    int mid = (l+r)/2;
    long long ch1 = query(t->l,l,mid+0);
    long long ch2 = query(t->r,mid+1,r);
    return gcd3(ch1,ch2);
}

long long Query(Tree *t, int l, int r)
{
    if(r<Ql||Qr<l||l>r||t==nullptr) return 0;
    if(Ql<=l&&r<=Qr)
    {
        long long ch = query(t->A,0,c-1);
        return ch;
    }
    int mid = (l+r)/2;
    long long ch1 = Query(t->L,l,mid+0);
    long long ch2 = Query(t->R,mid+1,r);
    return gcd3(ch1,ch2);
}

long long calculate(int P, int Q, int U, int V)
{
    ql = Q;
    qr = V;
    ///
    Ql = P;
    Qr = U;
    long long ans = Query(Root,0,r-1);
    return ans;
}

void init(int R, int C)
{
    r = R;
    c = C;
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20