oj.uz

Submission #218883

# Submission time Handle Problem Language Result Execution time Memory
218883 2020-04-03T01:10:36 Z Lawliet Game (IOI13_game) C++17
100 / 100
 5795 ms 41800 KB 
#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:

        friend class SparseSegmentTree;

        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, pnode newNode)
        {
            if( t == myNULL ) t = newNode;
            else if( t->y < newNode->y ) split( t , newNode->e , newNode->d , newNode->x ), t = newNode;
            else if( t->x < newNode->x ) insert( t->d , newNode );
            else insert( t->e , newNode );

            recalculate( t );
        }

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

        lli getGCDCell(pnode t, int x)
        {
            if( t == myNULL ) return 0;
            if( t->x == x ) return t->v;
            if( t->x > x ) return getGCDCell( t->e , x );
            if( t->x < x ) return getGCDCell( t->d , x );
        }

        void update(int Y, lli val)
        {
            if( find( root , Y ) ) modify( root , Y , val );
            else insert( root , new node( 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] ].getGCDCell( t[ e[node] ].root , Y );
            lli gcdRight = t[ d[node] ].getGCDCell( t[ d[node] ].root , 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 ); }

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;
      ^~~
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 'lli Treap::getGCDCell(pnode, int)':
game.cpp:108:9: warning: control reaches end of non-void function [-Wreturn-type]
         }
         ^
game.cpp: In member function 'bool Treap::find(pnode, lli)':
game.cpp:45:9: warning: control reaches end of non-void function [-Wreturn-type]
         }
         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 927 ms 7544 KB Output is correct
5 Correct 437 ms 7672 KB Output is correct
6 Correct 1216 ms 4588 KB Output is correct
7 Correct 1405 ms 4220 KB Output is correct
8 Correct 972 ms 4192 KB Output is correct
9 Correct 1341 ms 4472 KB Output is correct
10 Correct 1240 ms 3960 KB Output is correct
11 Correct 5 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 1302 ms 9336 KB Output is correct
13 Correct 3149 ms 4156 KB Output is correct
14 Correct 417 ms 1916 KB Output is correct
15 Correct 3228 ms 4796 KB Output is correct
16 Correct 309 ms 6648 KB Output is correct
17 Correct 2007 ms 5240 KB Output is correct
18 Correct 3235 ms 7288 KB Output is correct
19 Correct 2770 ms 7208 KB Output is correct
20 Correct 2523 ms 6576 KB Output is correct
21 Correct 4 ms 256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 903 ms 7592 KB Output is correct
13 Correct 442 ms 7764 KB Output is correct
14 Correct 1214 ms 4472 KB Output is correct
15 Correct 1401 ms 4728 KB Output is correct
16 Correct 975 ms 4088 KB Output is correct
17 Correct 1377 ms 4476 KB Output is correct
18 Correct 1220 ms 4088 KB Output is correct
19 Correct 1287 ms 9336 KB Output is correct
20 Correct 3164 ms 4516 KB Output is correct
21 Correct 417 ms 2040 KB Output is correct
22 Correct 3271 ms 5012 KB Output is correct
23 Correct 304 ms 6780 KB Output is correct
24 Correct 1990 ms 5368 KB Output is correct
25 Correct 3269 ms 7432 KB Output is correct
26 Correct 2782 ms 7452 KB Output is correct
27 Correct 2551 ms 6728 KB Output is correct
28 Correct 1165 ms 19280 KB Output is correct
29 Correct 2281 ms 22488 KB Output is correct
30 Correct 3964 ms 16860 KB Output is correct
31 Correct 3516 ms 13408 KB Output is correct
32 Correct 578 ms 1912 KB Output is correct
33 Correct 928 ms 2436 KB Output is correct
34 Correct 499 ms 19452 KB Output is correct
35 Correct 2335 ms 11484 KB Output is correct
36 Correct 4447 ms 19980 KB Output is correct
37 Correct 3551 ms 20076 KB Output is correct
38 Correct 3422 ms 19492 KB Output is correct
39 Correct 2967 ms 16200 KB Output is correct
40 Correct 5 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 907 ms 7416 KB Output is correct
13 Correct 442 ms 7928 KB Output is correct
14 Correct 1229 ms 4600 KB Output is correct
15 Correct 1423 ms 4216 KB Output is correct
16 Correct 997 ms 3960 KB Output is correct
17 Correct 1368 ms 4448 KB Output is correct
18 Correct 1237 ms 3960 KB Output is correct
19 Correct 1324 ms 9336 KB Output is correct
20 Correct 3180 ms 4504 KB Output is correct
21 Correct 432 ms 2040 KB Output is correct
22 Correct 3246 ms 4984 KB Output is correct
23 Correct 291 ms 6648 KB Output is correct
24 Correct 1998 ms 5368 KB Output is correct
25 Correct 3249 ms 7304 KB Output is correct
26 Correct 2777 ms 7484 KB Output is correct
27 Correct 2531 ms 6816 KB Output is correct
28 Correct 1165 ms 19288 KB Output is correct
29 Correct 2301 ms 22684 KB Output is correct
30 Correct 3972 ms 16860 KB Output is correct
31 Correct 3564 ms 13084 KB Output is correct
32 Correct 561 ms 2040 KB Output is correct
33 Correct 911 ms 2352 KB Output is correct
34 Correct 502 ms 19508 KB Output is correct
35 Correct 2328 ms 11676 KB Output is correct
36 Correct 4428 ms 19792 KB Output is correct
37 Correct 3538 ms 20032 KB Output is correct
38 Correct 3396 ms 19468 KB Output is correct
39 Correct 1514 ms 39748 KB Output is correct
40 Correct 3680 ms 41800 KB Output is correct
41 Correct 5795 ms 33536 KB Output is correct
42 Correct 4871 ms 25660 KB Output is correct
43 Correct 832 ms 40016 KB Output is correct
44 Correct 713 ms 2424 KB Output is correct
45 Correct 2979 ms 16356 KB Output is correct
46 Correct 5569 ms 40372 KB Output is correct
47 Correct 5555 ms 40240 KB Output is correct
48 Correct 5278 ms 39772 KB Output is correct
49 Correct 5 ms 256 KB Output is correct