Submission #93434

#	Time	Username	Problem	Language	Result	Execution time	Memory
93434		Bodo171	Game (IOI13_game)	C++14	100 / 100	4521 ms	56976 KiB

game

#include "game.h"
#include <climits>
#include <iostream>
#include <algorithm>
#include <map>
#include <ctime>
#include <cstdlib>
#define mp make_pair
using namespace std;
long long gcd(long long X, long long Y) {
    long long tmp;
    if(!X) return Y;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
static long long ans;
static int Rowss,Columnss;
static int X1,Y1,X2,Y2;
struct Treap
{
    Treap *ls,*rs;
    int pr,poz;
    long long G,sub;
    Treap()
    {
        ls=rs=0;
        pr=rand()+1;
        poz=0;
        G=sub=0;
    }
}*nil=new Treap;
void rec(Treap * &T)
{
    if(T->ls&&T->rs)T->sub=gcd(T->ls->sub,T->rs->sub);
    else T->sub=0;
    T->sub=gcd(T->sub,T->G);
}
void rotl(Treap* &T)
{
    Treap *aux=T;
    T=T->ls;
    aux->ls=T->rs;
    T->rs=aux;
    rec(T->rs);rec(T);
}
void rotr(Treap* &T)
{
    Treap *aux=T;
    T=T->rs;
    aux->rs=T->ls;
    T->ls=aux;
    rec(T->ls);rec(T);
}

void updY(Treap* &T,int poz,long long value)
{
    if(T->poz==poz)
    {
        T->G=value;
        rec(T);
        return;
    }
    if(T==nil)
    {
        T=new Treap;T->poz=poz;
        T->ls=nil;T->rs=nil;
        T->G=value;
        rec(T);
        return;
    }
    if(poz<T->poz) updY(T->ls,poz,value);
    else updY(T->rs,poz,value);
    if(T->ls->pr>T->pr) rotl(T);
    else if(T->rs->pr>T->pr) rotr(T);
    rec(T);
}
void qrY(Treap* &T,int l,int r)
{
    if(T==nil) return;
    if(T->poz>=Y1&&T->poz<=Y2)
    {
        ans=gcd(ans,T->G);
        if(l>=Y1)
        {
            ans=gcd(T->ls->sub,ans);
        }
        else
        {
            qrY(T->ls,l,T->poz);
        }
        if(r<=Y2)
        {
            ans=gcd(T->rs->sub,ans);
        }
        else
        {
            qrY(T->rs,T->poz,r);
        }
    }
    if(T->poz<Y1) qrY(T->rs,l,r);
    if(T->poz>Y2) qrY(T->ls,l,r);
}
struct aint
{
    aint *ls,*rs;
    Treap *nxt;
    aint()
    {
        ls=rs=0;nxt=0;
    }
}*rad;
void init(int R, int C) {
    Rowss=R;Columnss=C;
    rad=new aint;
    srand(time(NULL));
    nil->pr=0;
}
long long aux=0;
void print(Treap* T)
{
    if(T==nil)
        return;
    print(T->ls);
    cout<<T->poz<<' '<<T->G<<' '<<T->pr<<'\n';
    print(T->rs);
}
void updX(aint* &nod,int l,int r,int poz,int y,long long value)
{
    if(!nod->nxt)
    {
        nod->nxt=nil;
    }
    if(l==r)
    {
         updY(nod->nxt,y,value);
        return;
    }
    int m=(l+r)/2;
    if(poz<=m)
    {
        if(!nod->ls) nod->ls=new aint;
        updX(nod->ls,l,m,poz,y,value);
    }
    else
    {
        if(!nod->rs) nod->rs=new aint;
        updX(nod->rs,m+1,r,poz,y,value);
    }
    ans=0;Y1=Y2=y;
    if(nod->ls)qrY(nod->ls->nxt,0,Columnss+1);
    aux=ans;ans=0;
    if(nod->rs)qrY(nod->rs->nxt,0,Columnss+1);
    updY(nod->nxt,y,gcd(aux,ans));
}

void qrX(aint* &nod,int l,int r)
{
    if(X1<=l&&r<=X2)
    {
        if(nod->nxt) qrY(nod->nxt,1,Columnss);
        return;
    }
    int m=(l+r)/2;
    if(X1<=m&&nod->ls) qrX(nod->ls,l,m);
    if(m<X2&&nod->rs) qrX(nod->rs,m+1,r);
}
void update(int P, int Q, long long K) {
    P++,Q++;
    updX(rad,1,Rowss,P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    ans=0;
    P++,Q++,U++,V++;
    X1=P;Y1=Q;X2=U;Y2=V;
    qrX(rad,1,Rowss);
    return ans;
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

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