oj.uz

Submission #218880

# Submission time Handle Problem Language Result Execution time Memory
218880 2020-04-03T00:51:54 Z Lawliet Game (IOI13_game) C++14
100 / 100
 6803 ms 51568 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:

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

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 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 4 ms 256 KB Output is correct

Subtask #2
27.0 / 27.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 986 ms 10848 KB Output is correct
5 Correct 490 ms 10616 KB Output is correct
6 Correct 1363 ms 8416 KB Output is correct
7 Correct 1547 ms 7800 KB Output is correct
8 Correct 1040 ms 7160 KB Output is correct
9 Correct 1538 ms 8056 KB Output is correct
10 Correct 1347 ms 7672 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 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 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 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 1422 ms 12128 KB Output is correct
13 Correct 3318 ms 7160 KB Output is correct
14 Correct 464 ms 5624 KB Output is correct
15 Correct 3404 ms 8448 KB Output is correct
16 Correct 516 ms 9848 KB Output is correct
17 Correct 2095 ms 9208 KB Output is correct
18 Correct 3491 ms 11624 KB Output is correct
19 Correct 3029 ms 11508 KB Output is correct
20 Correct 2740 ms 11064 KB Output is correct
21 Correct 5 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 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 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 969 ms 10928 KB Output is correct
13 Correct 493 ms 10668 KB Output is correct
14 Correct 1357 ms 8184 KB Output is correct
15 Correct 1572 ms 8060 KB Output is correct
16 Correct 1063 ms 7448 KB Output is correct
17 Correct 1525 ms 7928 KB Output is correct
18 Correct 1342 ms 7672 KB Output is correct
19 Correct 1418 ms 12412 KB Output is correct
20 Correct 3315 ms 7160 KB Output is correct
21 Correct 472 ms 5624 KB Output is correct
22 Correct 3391 ms 8324 KB Output is correct
23 Correct 510 ms 9848 KB Output is correct
24 Correct 2093 ms 9080 KB Output is correct
25 Correct 3463 ms 11388 KB Output is correct
26 Correct 3084 ms 11420 KB Output is correct
27 Correct 2780 ms 11008 KB Output is correct
28 Correct 1273 ms 28960 KB Output is correct
29 Correct 2307 ms 31472 KB Output is correct
30 Correct 4318 ms 22636 KB Output is correct
31 Correct 3809 ms 19448 KB Output is correct
32 Correct 621 ms 10104 KB Output is correct
33 Correct 986 ms 10500 KB Output is correct
34 Correct 766 ms 25300 KB Output is correct
35 Correct 2479 ms 20228 KB Output is correct
36 Correct 4713 ms 29460 KB Output is correct
37 Correct 3832 ms 29608 KB Output is correct
38 Correct 3741 ms 28968 KB Output is correct
39 Correct 3207 ms 25404 KB Output is correct
40 Correct 4 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 6 ms 416 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 4 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 1006 ms 11128 KB Output is correct
13 Correct 532 ms 10744 KB Output is correct
14 Correct 1368 ms 8300 KB Output is correct
15 Correct 1540 ms 8060 KB Output is correct
16 Correct 1054 ms 7388 KB Output is correct
17 Correct 1497 ms 8312 KB Output is correct
18 Correct 1338 ms 7544 KB Output is correct
19 Correct 1402 ms 12280 KB Output is correct
20 Correct 3301 ms 7496 KB Output is correct
21 Correct 470 ms 5624 KB Output is correct
22 Correct 3468 ms 8344 KB Output is correct
23 Correct 513 ms 9796 KB Output is correct
24 Correct 2089 ms 9036 KB Output is correct
25 Correct 3542 ms 11636 KB Output is correct
26 Correct 3109 ms 11416 KB Output is correct
27 Correct 2737 ms 10804 KB Output is correct
28 Correct 1269 ms 29004 KB Output is correct
29 Correct 2415 ms 31672 KB Output is correct
30 Correct 4389 ms 22596 KB Output is correct
31 Correct 3873 ms 19268 KB Output is correct
32 Correct 640 ms 10232 KB Output is correct
33 Correct 1012 ms 10616 KB Output is correct
34 Correct 789 ms 25356 KB Output is correct
35 Correct 2527 ms 20452 KB Output is correct
36 Correct 4855 ms 29560 KB Output is correct
37 Correct 3823 ms 29776 KB Output is correct
38 Correct 3705 ms 29136 KB Output is correct
39 Correct 1762 ms 49372 KB Output is correct
40 Correct 4008 ms 51568 KB Output is correct
41 Correct 6803 ms 40000 KB Output is correct
42 Correct 5784 ms 31992 KB Output is correct
43 Correct 1530 ms 46168 KB Output is correct
44 Correct 982 ms 10616 KB Output is correct
45 Correct 3257 ms 25324 KB Output is correct
46 Correct 6587 ms 50448 KB Output is correct
47 Correct 6348 ms 50224 KB Output is correct
48 Correct 6028 ms 49736 KB Output is correct
49 Correct 5 ms 256 KB Output is correct