oj.uz

Submission #229645

# Submission time Handle Problem Language Result Execution time Memory
229645 2020-05-05T14:45:17 Z CaroLinda Game (IOI13_game) C++14
100 / 100
 7175 ms 251528 KB 
#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 ;

using namespace std ;

int Y[MAXN] ;

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 Treap
{
    int l1, r1, l2, r2 ;
    vector<int> y , L , R ;
    vector<ll> mdc , val ;
    int rt = 0 ;

    inline void calc(int u)
    {
        mdc[u] = gcd2( mdc[ L[u] ] , mdc[ R[u] ] ) ;
        mdc[u] = gcd2( mdc[u] , val[u] ) ;
    }

    int merge(int l, int r)
    {
        if(!l || !r) return l + r ;
        int u;
        if( Y[l] > Y[r] ) { R[l] = merge(R[l] , r ) ; u = l ; }
        else { L[r] = merge( l , L[r] ) ; u = r ; }
        calc(u) ;
        return u ;
    }

    void splitY(int u , int &l, int &r, int x)
    {

        if( u == 0 ) return (void)( l = r= 0 ) ;

        if( y[u] <= x )
        {
            splitY( R[u] , l , r , x ) ;
            R[u] = l ;
            l = u ;
        }
        else
        {
            splitY( L[u] , l, r , x ) ;
            L[u] = r ;
            r = u ;
        }
        calc(u) ;
    }

    int create(int _y, ll x)
    {
        y.pb(_y) ;
        L.pb(0) ;
        R.pb(0) ;
        val.pb(x) ;
        mdc.pb(x) ;
        return y.size() - 1 ;
    }

    Treap() { create(-1,0) ; }

    inline void upd(int _y , ll x )
    {

        splitY( rt , l1 , r1 , _y ) ;
        splitY( l1, l2, r2, _y - 1 ) ;

        if( r2 == 0 ) r2 = create( _y , x ) ;
        val[r2] = x ;
        calc(r2) ;

        l1 = merge(l2, r2) ;
        rt = merge(l1, r1) ;

    }

    ll qry( int _y1, int _y2 )
    {

        splitY( rt , l1 , r1 , _y2 ) ;
        splitY( l1, l2, r2, _y1-1 ) ;

        ll resp = mdc[r2] ;

        l1 = merge(l2,r2) ;
        rt = merge(l1, r1) ;

        return resp ;

    }

};

struct Seg
{

    vector<Treap> treap ;
    vector<int> e , d ;

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

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

        create() ;
        create() ;
    }

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

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

        treap[pos].upd( 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 treap[pos].qry( 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) {
    srand( time(0) ) ;
    seg.init() ;
    lp(i,0,MAXN) Y[i] = i ;
    random_shuffle(Y, Y+MAXN) ;
}

void update(int P, int Q, long long K) { seg.upd( 1 , 0  , MAX , P , Q , K )  ;}

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

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 1619 ms 20488 KB Output is correct
5 Correct 1136 ms 20344 KB Output is correct
6 Correct 2423 ms 16760 KB Output is correct
7 Correct 2515 ms 16736 KB Output is correct
8 Correct 1457 ms 12152 KB Output is correct
9 Correct 2566 ms 16968 KB Output is correct
10 Correct 2144 ms 16356 KB Output is correct
11 Correct 5 ms 384 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 9 ms 640 KB Output is correct
3 Correct 9 ms 640 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 9 ms 640 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 8 ms 512 KB Output is correct
10 Correct 8 ms 512 KB Output is correct
11 Correct 7 ms 512 KB Output is correct
12 Correct 1826 ms 14052 KB Output is correct
13 Correct 3318 ms 8584 KB Output is correct
14 Correct 710 ms 5496 KB Output is correct
15 Correct 3525 ms 10952 KB Output is correct
16 Correct 1085 ms 13096 KB Output is correct
17 Correct 2561 ms 11632 KB Output is correct
18 Correct 4321 ms 14040 KB Output is correct
19 Correct 3951 ms 14028 KB Output is correct
20 Correct 3300 ms 13724 KB Output is correct
21 Correct 5 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 9 ms 640 KB Output is correct
3 Correct 9 ms 640 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 9 ms 640 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 8 ms 640 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 1662 ms 20404 KB Output is correct
13 Correct 1088 ms 20384 KB Output is correct
14 Correct 2369 ms 17096 KB Output is correct
15 Correct 2506 ms 16972 KB Output is correct
16 Correct 1515 ms 12136 KB Output is correct
17 Correct 2530 ms 16824 KB Output is correct
18 Correct 2132 ms 16508 KB Output is correct
19 Correct 1826 ms 13796 KB Output is correct
20 Correct 3302 ms 8464 KB Output is correct
21 Correct 702 ms 5368 KB Output is correct
22 Correct 3499 ms 11048 KB Output is correct
23 Correct 1116 ms 12836 KB Output is correct
24 Correct 2632 ms 11728 KB Output is correct
25 Correct 4387 ms 14092 KB Output is correct
26 Correct 3931 ms 14280 KB Output is correct
27 Correct 3256 ms 13484 KB Output is correct
28 Correct 1659 ms 118032 KB Output is correct
29 Correct 2884 ms 122756 KB Output is correct
30 Correct 4606 ms 71968 KB Output is correct
31 Correct 4013 ms 55904 KB Output is correct
32 Correct 679 ms 4144 KB Output is correct
33 Correct 1144 ms 5440 KB Output is correct
34 Correct 1896 ms 119844 KB Output is correct
35 Correct 2849 ms 63876 KB Output is correct
36 Correct 4897 ms 118564 KB Output is correct
37 Correct 4241 ms 118684 KB Output is correct
38 Correct 3832 ms 118700 KB Output is correct
39 Correct 3595 ms 107764 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 5 ms 384 KB Output is correct
2 Correct 10 ms 640 KB Output is correct
3 Correct 9 ms 640 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 11 ms 640 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 8 ms 640 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 7 ms 512 KB Output is correct
12 Correct 1693 ms 20704 KB Output is correct
13 Correct 1156 ms 20292 KB Output is correct
14 Correct 2335 ms 17416 KB Output is correct
15 Correct 2414 ms 17016 KB Output is correct
16 Correct 1491 ms 12152 KB Output is correct
17 Correct 2457 ms 17016 KB Output is correct
18 Correct 2137 ms 16628 KB Output is correct
19 Correct 1826 ms 13668 KB Output is correct
20 Correct 3517 ms 8736 KB Output is correct
21 Correct 679 ms 5912 KB Output is correct
22 Correct 3509 ms 11072 KB Output is correct
23 Correct 1186 ms 12992 KB Output is correct
24 Correct 2573 ms 11940 KB Output is correct
25 Correct 4337 ms 14212 KB Output is correct
26 Correct 3870 ms 14568 KB Output is correct
27 Correct 3214 ms 13752 KB Output is correct
28 Correct 1646 ms 118432 KB Output is correct
29 Correct 2798 ms 122176 KB Output is correct
30 Correct 4545 ms 72504 KB Output is correct
31 Correct 4125 ms 56732 KB Output is correct
32 Correct 671 ms 4600 KB Output is correct
33 Correct 1131 ms 6124 KB Output is correct
34 Correct 1923 ms 120540 KB Output is correct
35 Correct 2860 ms 64668 KB Output is correct
36 Correct 4907 ms 119496 KB Output is correct
37 Correct 4172 ms 119476 KB Output is correct
38 Correct 3845 ms 119212 KB Output is correct
39 Correct 2449 ms 249068 KB Output is correct
40 Correct 4750 ms 251528 KB Output is correct
41 Correct 7175 ms 146776 KB Output is correct
42 Correct 6525 ms 112844 KB Output is correct
43 Correct 3049 ms 245868 KB Output is correct
44 Correct 1081 ms 10900 KB Output is correct
45 Correct 3663 ms 115516 KB Output is correct
46 Correct 6931 ms 250352 KB Output is correct
47 Correct 6980 ms 250316 KB Output is correct
48 Correct 6084 ms 249808 KB Output is correct
49 Correct 5 ms 384 KB Output is correct