oj.uz

Submission #93427

# Submission time Handle Problem Language Result Execution time Memory
93427 2019-01-08T11:38:59 Z Bodo171 Game (IOI13_game) C++14
0 / 100
 648 ms 11292 KB 
#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);rec(T->rs);
}
void rotr(Treap* &T)
{
    Treap *aux=T;
    T=T->rs;
    aux->rs=T->ls;
    T->ls=aux;
    rec(T);rec(T->ls);
}

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);
}
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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Incorrect 648 ms 11292 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 10 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 372 KB Output isn't correct
3 Halted 0 ms 0 KB -