Submission #229645

#	Time	Username	Problem	Language	Result	Execution time	Memory
229645		CaroLinda	Game (IOI13_game)	C++14	100 / 100	7175 ms	251528 KiB

game

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

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#define mkt make_tuple
#define debug printf
#define all(x) x.begin(),x.end()
#define lp(i,a,b) for(int i = a ; i< b ; i++)
#define ss second
#define ff first
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mk make_pair

const int MAXN = 22010 ;
const int MAX = 1e9+5 ;

using namespace std ;

int Y[MAXN] ;

long long gcd2(long long X, long long Y) {
    long long tmp;
    if( X < Y ) swap(X,Y) ;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

int m(int l, int r) { return (l+r)>>1 ; }

struct Treap
{
    int l1, r1, l2, r2 ;
    vector<int> y , L , R ;
    vector<ll> mdc , val ;
    int rt = 0 ;

    inline void calc(int u)
    {
        mdc[u] = gcd2( mdc[ L[u] ] , mdc[ R[u] ] ) ;
        mdc[u] = gcd2( mdc[u] , val[u] ) ;
    }

    int merge(int l, int r)
    {
        if(!l || !r) return l + r ;
        int u;
        if( Y[l] > Y[r] ) { R[l] = merge(R[l] , r ) ; u = l ; }
        else { L[r] = merge( l , L[r] ) ; u = r ; }
        calc(u) ;
        return u ;
    }

    void splitY(int u , int &l, int &r, int x)
    {

        if( u == 0 ) return (void)( l = r= 0 ) ;

        if( y[u] <= x )
        {
            splitY( R[u] , l , r , x ) ;
            R[u] = l ;
            l = u ;
        }
        else
        {
            splitY( L[u] , l, r , x ) ;
            L[u] = r ;
            r = u ;
        }
        calc(u) ;
    }

    int create(int _y, ll x)
    {
        y.pb(_y) ;
        L.pb(0) ;
        R.pb(0) ;
        val.pb(x) ;
        mdc.pb(x) ;
        return y.size() - 1 ;
    }

    Treap() { create(-1,0) ; }

    inline void upd(int _y , ll x )
    {

        splitY( rt , l1 , r1 , _y ) ;
        splitY( l1, l2, r2, _y - 1 ) ;

        if( r2 == 0 ) r2 = create( _y , x ) ;
        val[r2] = x ;
        calc(r2) ;

        l1 = merge(l2, r2) ;
        rt = merge(l1, r1) ;

    }

    ll qry( int _y1, int _y2 )
    {

        splitY( rt , l1 , r1 , _y2 ) ;
        splitY( l1, l2, r2, _y1-1 ) ;

        ll resp = mdc[r2] ;

        l1 = merge(l2,r2) ;
        rt = merge(l1, r1) ;

        return resp ;

    }

};

struct Seg
{

    vector<Treap> treap ;
    vector<int> e , d ;

    int create()
    {
        e.pb(0) ;
        d.pb(0) ;
        treap.pb( *(new Treap) ) ;
        return e.size() - 1 ;
    }

    inline void init()
    {
        e.clear() ;
        d.clear() ;
        treap.clear() ;

        create() ;
        create() ;
    }

    void upd(int pos, int l, int r, int x, int y, ll val )
    {

        if( l == r )
        {
            treap[pos].upd(  y , val ) ;
            return ;
        }

        int aux ;

        if( x <= m(l,r) )
        {
            if( e[pos] == 0  ){ aux = create() ; e[pos] = aux ; }
            upd( e[pos] , l , m(l,r) , x , y , val ) ;
        }
        else
        {
            if( d[pos] == 0 ) { aux = create() ; d[pos] = aux ; }
            upd(d[pos] , m(l,r)+1, r, x, y, val ) ;
        }

        ll al = treap[ e[pos] ].qry( y , y  ) ;
        ll ar = treap[ d[pos] ].qry( y , y ) ;

        treap[pos].upd( y , gcd2( al , ar ) ) ;

    }

    ll qry(int pos, int l, int r, int x1, int x2, int y1, int y2)
    {

        if( l >  x2 || r < x1 || pos == 0 ) return 0LL ;
        if( l >= x1 && r <= x2 ) return treap[pos].qry( y1, y2 ) ;

        ll al = qry( e[pos] , l, m(l,r) , x1, x2, y1, y2 ) ;
        ll ar = qry( d[pos] , m(l,r)+1 , r , x1, x2, y1, y2 ) ;

        return gcd2(al,ar) ;

    }

};

int R , C , N ;
int type , p , q , u , v ;
ll k ;
Seg seg;

long long calculate(int P, int Q, int U, int V) { return seg.qry(1,0,MAX, P, U, Q, V) ; }

void init(int R, int C) {
    srand( time(0) ) ;
    seg.init() ;
    lp(i,0,MAXN) Y[i] = i ;
    random_shuffle(Y, Y+MAXN) ;
}

void update(int P, int Q, long long K) { seg.upd( 1 , 0  , MAX , P , Q , K )  ;}

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;
      ^~~
game.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
game.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")

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