oj.uz

Submission #218882

# Submission time Handle Problem Language Result Execution time Memory
218882 2020-04-03T00:59:53 Z Lawliet Game (IOI13_game) C++14
100 / 100
 6058 ms 41980 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, 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;
        }

        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 , 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 'void Treap::insert(node*&, int, lli)':
game.cpp:70:25: warning: unused variable 'c' [-Wunused-variable]
             pnode a, b, c;
                         ^
game.cpp: In member function 'lli Treap::getGCDCell(pnode, int)':
game.cpp:107: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 384 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 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 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 4 ms 256 KB Output is correct
4 Correct 973 ms 8696 KB Output is correct
5 Correct 477 ms 8936 KB Output is correct
6 Correct 1273 ms 5752 KB Output is correct
7 Correct 1452 ms 5496 KB Output is correct
8 Correct 1008 ms 5212 KB Output is correct
9 Correct 1410 ms 5624 KB Output is correct
10 Correct 1295 ms 5244 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 4 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 384 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 1356 ms 10436 KB Output is correct
13 Correct 3195 ms 5628 KB Output is correct
14 Correct 428 ms 3208 KB Output is correct
15 Correct 3287 ms 6036 KB Output is correct
16 Correct 344 ms 7916 KB Output is correct
17 Correct 2029 ms 6400 KB Output is correct
18 Correct 3279 ms 8584 KB Output is correct
19 Correct 2825 ms 8596 KB Output is correct
20 Correct 2600 ms 7752 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 4 ms 256 KB Output is correct
2 Correct 5 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 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 6 ms 384 KB Output is correct
12 Correct 978 ms 8696 KB Output is correct
13 Correct 473 ms 8984 KB Output is correct
14 Correct 1292 ms 5752 KB Output is correct
15 Correct 1467 ms 5500 KB Output is correct
16 Correct 1031 ms 5224 KB Output is correct
17 Correct 1423 ms 5504 KB Output is correct
18 Correct 1280 ms 5240 KB Output is correct
19 Correct 1330 ms 10232 KB Output is correct
20 Correct 3186 ms 5368 KB Output is correct
21 Correct 430 ms 3192 KB Output is correct
22 Correct 3281 ms 5916 KB Output is correct
23 Correct 335 ms 7868 KB Output is correct
24 Correct 2024 ms 6688 KB Output is correct
25 Correct 3305 ms 8376 KB Output is correct
26 Correct 2826 ms 8448 KB Output is correct
27 Correct 2615 ms 7800 KB Output is correct
28 Correct 1203 ms 20736 KB Output is correct
29 Correct 2324 ms 23640 KB Output is correct
30 Correct 4113 ms 17700 KB Output is correct
31 Correct 3652 ms 14560 KB Output is correct
32 Correct 574 ms 3192 KB Output is correct
33 Correct 934 ms 3576 KB Output is correct
34 Correct 550 ms 20428 KB Output is correct
35 Correct 2405 ms 12648 KB Output is correct
36 Correct 4524 ms 21032 KB Output is correct
37 Correct 3579 ms 20964 KB Output is correct
38 Correct 3503 ms 20420 KB Output is correct
39 Correct 3015 ms 17500 KB Output is correct
40 Correct 5 ms 384 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 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 983 ms 8224 KB Output is correct
13 Correct 457 ms 8484 KB Output is correct
14 Correct 1287 ms 5260 KB Output is correct
15 Correct 1449 ms 5244 KB Output is correct
16 Correct 996 ms 4908 KB Output is correct
17 Correct 1416 ms 5240 KB Output is correct
18 Correct 1262 ms 4984 KB Output is correct
19 Correct 1348 ms 9892 KB Output is correct
20 Correct 3160 ms 5064 KB Output is correct
21 Correct 423 ms 2764 KB Output is correct
22 Correct 3281 ms 5792 KB Output is correct
23 Correct 342 ms 7320 KB Output is correct
24 Correct 2077 ms 5932 KB Output is correct
25 Correct 3338 ms 7828 KB Output is correct
26 Correct 2845 ms 8032 KB Output is correct
27 Correct 2579 ms 7456 KB Output is correct
28 Correct 1189 ms 20048 KB Output is correct
29 Correct 2275 ms 23060 KB Output is correct
30 Correct 4114 ms 17056 KB Output is correct
31 Correct 3576 ms 13560 KB Output is correct
32 Correct 568 ms 2552 KB Output is correct
33 Correct 926 ms 2936 KB Output is correct
34 Correct 549 ms 20052 KB Output is correct
35 Correct 2352 ms 11704 KB Output is correct
36 Correct 4511 ms 20104 KB Output is correct
37 Correct 3566 ms 20296 KB Output is correct
38 Correct 3445 ms 19804 KB Output is correct
39 Correct 1605 ms 39872 KB Output is correct
40 Correct 3673 ms 41980 KB Output is correct
41 Correct 6058 ms 33676 KB Output is correct
42 Correct 5028 ms 25972 KB Output is correct
43 Correct 962 ms 39908 KB Output is correct
44 Correct 721 ms 2040 KB Output is correct
45 Correct 3022 ms 16224 KB Output is correct
46 Correct 5735 ms 40224 KB Output is correct
47 Correct 5673 ms 39964 KB Output is correct
48 Correct 5385 ms 39756 KB Output is correct
49 Correct 4 ms 256 KB Output is correct