제출 #218880

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
218880		Lawliet	Game (IOI13_game)	C++14	100 / 100	6803 ms	51568 KiB

game

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

using namespace std;
typedef long long int lli;
typedef struct node* pnode;

pnode myNULL;

struct node
{
    int x, y;
    lli v, gcd;

    pnode e, d;

    node(int x, lli val)
        : e(myNULL), d(myNULL), x(x), y( rand() ), v(val), gcd(val) {}
};

lli gcd(lli A, lli B)
{
    if( B == 0 ) return A;
    return gcd( B , A%B );
}

class Treap
{
    public:

        void recalculate(pnode t)
        {
            t->gcd = gcd( t->e->gcd , t->d->gcd );
            t->gcd = gcd( t->gcd , t->v );
        }

        bool find(pnode t, lli cur)
        {
            if( t == myNULL ) return false;
            if( t->x == cur ) return true;
            if( t->x > cur ) return find( t->e , cur );
            if( t->x < cur ) return find( t->d , cur );
        }

        void merge(pnode& t, pnode l, pnode r)
        {
            if( l == myNULL ) return void( t = r );
            if( r == myNULL ) return void( t = l );

            if( l->y < r->y ) merge( r->e , l , r->e ), t = r;
            else merge( l->d , l->d , r ), t = l;

            recalculate( t );
        }

        void split(pnode t, pnode& l, pnode& r, int k)
        {
            if( t == myNULL ) return void( l = r = myNULL );

            if( t->x < k ) split( t->d , t->d , r , k ), l = t;
            else split( t->e , l , t->e , k ), r = t;

            recalculate( t );
        }

        void insert(pnode& t, int i, lli v)
        {
            pnode a, b, c;

            split( t , a , b , i );
            merge( t , a , new node( i , v ) );
            merge( t , t , b );
        }

        void modify(pnode t, int x, lli v)
        {
            if( t->x == x ) t->v = v;
            if( t->x > x ) modify( t->e , x , v );
            if( t->x < x ) modify( t->d , x , v );

            recalculate( t );
        }

        lli query(int Y1, int Y2)
        {
            pnode left, center, right;

            split( root , left , center , Y1 );
            split( center , center , right , Y2 + 1 );

            lli ans = center->gcd;

            merge( root , left , center );
            merge( root , root , right );

            return ans;
        }

        void update(int Y, lli val)
        {
            if( find( root , Y ) ) modify( root , Y , val );
            else insert( root , Y , val );
        }

        Treap() { root = myNULL; }

    private:

        pnode root;
};

class SparseSegmentTree
{
    public:

        void create()
        {
            e.push_back( 0 );
            d.push_back( 0 );
            t.push_back( Treap() );
        }

        int getLeft(int node)
        {
            if( e[node] == 0 )
            {
                e[node] = ++cntNode;
                create();
            }

            return e[node];
        }

        int getRight(int node)
        {
            if( d[node] == 0 )
            {
                d[node] = ++cntNode;
                create();
            }

            return d[node];
        }

        void update(int node, int l, int r, int X, int Y, lli v)
        {
            if( l == r )
            {
                t[node].update( Y , v );
                return;
            }

            int m = ( l + r )/2;

            if( X <= m ) update( getLeft(node) , l , m , X , Y , v );
            else update( getRight(node) , m + 1 , r , X , Y , v );

            lli gcdLeft = t[ e[node] ].query( Y , Y );
            lli gcdRight = t[ d[node] ].query( Y , Y );

            t[node].update( Y , gcd( gcdLeft , gcdRight ) );
        }

        lli query(int node, int l, int r, int X1, int Y1, int X2, int Y2)
        {
            if( node == 0 ) return 0;
            if( X2 < l || r < X1 ) return 0;

            if( X1 <= l && r <= X2 ) return t[node].query( Y1 , Y2 );

            int m = ( l + r )/2;

            lli gcdLeft = query( e[node] , l , m , X1 , Y1 , X2 , Y2 );
            lli gcdRight = query( d[node] , m + 1 , r , X1 , Y1 , X2 , Y2 );

            return gcd( gcdLeft , gcdRight );
        }

        void init() { create(); create(); }

        SparseSegmentTree() : cntNode(1) {}

    private:

        int cntNode;

        vector< int > e, d;
        vector< Treap > t;
};

int n, m;

SparseSegmentTree SEG;

void init(int R, int C) 
{
    n = R - 1;
    m = C - 1;

    myNULL = new node( 0 , 0 );
    SEG.init();
}

void update(int P, int Q, long long K) { SEG.update( 1 , 0 , n , P , Q , K ); }

long long calculate(int P, int Q, int U, int V) { return SEG.query( 1 , 0 , n , P , Q , U , V ); }

컴파일 시 표준 에러 (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: In constructor 'node::node(int, lli)':
game.cpp:15:14: warning: 'node::d' will be initialized after [-Wreorder]
     pnode e, d;
              ^
game.cpp:12:9: warning:   'int node::x' [-Wreorder]
     int x, y;
         ^
game.cpp:17:5: warning:   when initialized here [-Wreorder]
     node(int x, lli val)
     ^~~~
game.cpp: In member function 'void Treap::insert(node*&, int, lli)':
game.cpp:68:25: warning: unused variable 'c' [-Wunused-variable]
             pnode a, b, c;
                         ^
game.cpp: In member function 'bool Treap::find(pnode, lli)':
game.cpp:43:9: warning: control reaches end of non-void function [-Wreturn-type]
         }
         ^

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