Submission #503955

#	Time	Username	Problem	Language	Result	Execution time	Memory
503955		stefantaga	Game (IOI13_game)	C++14	100 / 100	3190 ms	82248 KiB

game

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

using namespace std;
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
typedef long long ll;
int n,m;
struct nodex
{
    int st,dr;
    nodex *fiust,*fiudr;
    long long val;
    nodex(int stanga,int dreapta)
    {
        st=stanga;
        dr=dreapta;
        val=0;
        fiust=fiudr=nullptr;
    }
};
struct nodey
{
    nodey(int stanga,int dreapta) : st(stanga), dr(dreapta), fiust(NULL), fiudr(NULL), fiux(1,m) {}
    int st,dr;
    nodex fiux;
    nodey *fiust,*fiudr;
}*root;
ll query2(nodex *arb, int st,int dr)
{
    if (arb == nullptr || arb->st>dr||st>arb->dr)
    {
        return 0;
    }
    if (st<=arb->st&&arb->dr<=dr)
    {
        return arb->val;
    }
    int mij=(arb->st+arb->dr)/2;
    return gcd2(
        query2(arb->fiust,st,dr),
        query2(arb->fiudr,st,dr)
    );
}
ll query1(nodey *arb ,int st,int dr,int p,int q,int u ,int v)
{
    if (arb == NULL || st > u || dr<p)
    {
        return 0;
    }
    if (p<=st && dr<=u)
    {
        return query2(&arb->fiux,q,v);
    }
    int mij=(st+dr)/2;
    return gcd2(
        query1(arb->fiust,st,mij,p,q,u,v),
        query1(arb->fiudr,mij+1,dr,p,q,u,v)
    );
}
void init(int R, int C) {
    n=R;
    m=C;
    root = new nodey(1,n);
}
void updatey(nodex *arb,int y,ll k)
{
     int st = arb->st, dr = arb->dr, mij=(st+dr)/2;
     if (st==dr)
     {
         arb->val=k;
         return;
     }
     nodex **copil = &(y<=mij ? arb->fiust : arb->fiudr);
     if (*copil == NULL)
     {
         *copil = new nodex (y,y);
         (*copil)->val = k;
     }
     else
     if ((*copil)->st<=y&&y<=(*copil)->dr)
     {
         updatey(*copil,y,k);
     }
     else
     {
         do
         {
             if (y<=mij)
             {
                 dr=mij;
             }
             else
             {
                 st=mij+1;
             }
             mij=(st+dr)/2;
         }while ((y<=mij) == ((*copil)->dr<=mij));
         nodex *nnode = new nodex(st,dr);
         if ((*copil)->dr<=mij)
         {
             nnode->fiust = *copil;
         }
         else
         {
             nnode->fiudr = *copil;
         }
         *copil=nnode;
         updatey(*copil,y,k);
     }
     arb->val = gcd2(
         arb->fiust ? arb->fiust->val : 0 ,
         arb->fiudr ? arb->fiudr->val : 0
     );
}
void updatex(nodey *arb, int st,int dr,int x,int y,long long k)
{
    int mij=(st+dr)/2;
    if (st==dr)
    {
        updatey(&arb->fiux,y,k);
        return;
    }
    if (x<=mij)
    {
        if (arb->fiust==NULL)
        {
            arb->fiust=new nodey(st,mij);
        }
        updatex(arb->fiust,st,mij,x,y,k);
    }
    else
    {
        if (arb->fiudr==NULL)
        {
            arb->fiudr= new nodey(mij+1,dr);
        }
        updatex(arb->fiudr,mij+1,dr,x,y,k);
    }
    ll val = gcd2(
       arb->fiust ? query2(&arb->fiust->fiux,y,y) : 0,
       arb->fiudr ? query2(&arb->fiudr->fiux,y,y) : 0
    );
    updatey(&arb->fiux,y,val);
}
void update(int P, int Q, long long K) {
    P++;
    Q++;
    updatex(root,1,n,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
    P++;Q++;U++;V++;
    return query1(root ,1,n,P,Q,U,V);
}
#ifdef HOME
int main()
{
    int n,m,q;
    ifstream cin("date.in");
    ofstream cout("date.out");
    cin>>n>>m>>q;
    init(n,m);
    for (;q--;)
    {
        int tip;
        cin>>tip;
        if (tip==1)
        {
            long long x,y,val;
            cin>>x>>y>>val;
            update(x,y,val);
        }
        else
        {
            long long p,q,u,v;
            cin>>p>>q>>u>>v;
            cout<<calculate(p,q,u,v)<<'\n';
        }
    }
    return 0;
}
#endif // HOME

Compilation message (stderr)

game.cpp: In constructor 'nodey::nodey(int, int)':
game.cpp:34:19: warning: 'nodey::fiudr' will be initialized after [-Wreorder]
   34 |     nodey *fiust,*fiudr;
      |                   ^~~~~
game.cpp:33:11: warning:   'nodex nodey::fiux' [-Wreorder]
   33 |     nodex fiux;
      |           ^~~~
game.cpp:31:5: warning:   when initialized here [-Wreorder]
   31 |     nodey(int stanga,int dreapta) : st(stanga), dr(dreapta), fiust(NULL), fiudr(NULL), fiux(1,m) {}
      |     ^~~~~
game.cpp: In function 'll query2(nodex*, int, int)':
game.cpp:46:9: warning: unused variable 'mij' [-Wunused-variable]
   46 |     int mij=(arb->st+arb->dr)/2;
      |         ^~~

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