Submission #229637

#	Time	Username	Problem	Language	Result	Execution time	Memory
229637		CaroLinda	Game (IOI13_game)	C++14	80 / 100	4232 ms	256008 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 ;
const int SQ = 150 ;

using namespace std ;

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 Sparse_seg
{

    vector<int> e , d ;
    vector<ll> mdc ;

    int create()
    {
        e.pb(0) ;
        d.pb(0) ;
        mdc.pb(0) ;
        return e.size() - 1 ;
    }

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

        create() ;
        create();
    }

    Sparse_seg() { init() ; }

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

        if(l==r) return (void)( mdc[pos] = val ) ;

        int aux ;

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

        mdc[pos] = gcd2( mdc[ e[pos] ] , mdc[ d[pos] ] ) ;

    }

    ll qry(int pos, int l , int r, int beg, int en)
    {
        if( l > en || r < beg || pos == 0 ) return 0LL ;
        if( l >= beg && r <= en ) return mdc[pos];

        ll al = qry( e[pos] , l , m(l,r) , beg, en ) ;
        ll ar= qry(d[pos] , m(l,r) + 1 , r ,beg, en) ;

        return gcd2(al, ar) ;

    }

};

struct Seg
{

    vector<Sparse_seg> tree ;
    vector<int> e , d ;

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

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

        create() ;
        create() ;
    }

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

        if( l == r )
        {
            tree[pos].upd( 1 , 0 , MAX , 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 = tree[ e[pos] ].qry( 1 , 0 , MAX , y , y  ) ;
        ll ar = tree[ d[pos] ].qry( 1 , 0 , MAX , y , y ) ;

        tree[pos].upd(1 , 0 , MAX , 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 tree[pos].qry( 1 , 0 , MAX , 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) { seg.init() ; }

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: 0 / 20