oj.uz

Submission #229637

# Submission time Handle Problem Language Result Execution time Memory
229637 2020-05-05T13:53:59 Z CaroLinda Game (IOI13_game) C++14
80 / 100
 4232 ms 256008 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 ;
const int SQ = 150 ;

using namespace std ;

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 Sparse_seg
{

    vector<int> e , d ;
    vector<ll> mdc ;

    int create()
    {
        e.pb(0) ;
        d.pb(0) ;
        mdc.pb(0) ;
        return e.size() - 1 ;
    }

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

        create() ;
        create();
    }

    Sparse_seg() { init() ; }

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

        if(l==r) return (void)( mdc[pos] = val ) ;

        int aux ;

        if( idx <= m(l,r) )
        {
            if( e[pos] == 0  ) { aux = create() ; e[pos] = aux ; }
            upd( e[pos] , l , m(l,r) , idx , val ) ;
        }
        else
        {
            if( d[pos] == 0 ) { aux = create() ; d[pos] = aux ; }
            upd(d[pos] , m(l,r)+1, r, idx, val) ;
        }

        mdc[pos] = gcd2( mdc[ e[pos] ] , mdc[ d[pos] ] ) ;

    }

    ll qry(int pos, int l , int r, int beg, int en)
    {
        if( l > en || r < beg || pos == 0 ) return 0LL ;
        if( l >= beg && r <= en ) return mdc[pos];

        ll al = qry( e[pos] , l , m(l,r) , beg, en ) ;
        ll ar= qry(d[pos] , m(l,r) + 1 , r ,beg, en) ;

        return gcd2(al, ar) ;

    }

};

struct Seg
{

    vector<Sparse_seg> tree ;
    vector<int> e , d ;

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

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

        create() ;
        create() ;
    }

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

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

        tree[pos].upd(1 , 0 , MAX , 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 tree[pos].qry( 1 , 0 , MAX , 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) { seg.init() ; }

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 8 ms 640 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 8 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 7 ms 640 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 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 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 1140 ms 35676 KB Output is correct
5 Correct 1006 ms 35492 KB Output is correct
6 Correct 1304 ms 32904 KB Output is correct
7 Correct 1296 ms 32504 KB Output is correct
8 Correct 788 ms 21452 KB Output is correct
9 Correct 1230 ms 32872 KB Output is correct
10 Correct 1146 ms 32364 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 8 ms 616 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 256 KB Output is correct
6 Correct 7 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 7 ms 640 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 1611 ms 19420 KB Output is correct
13 Correct 1851 ms 11020 KB Output is correct
14 Correct 719 ms 5880 KB Output is correct
15 Correct 2184 ms 15036 KB Output is correct
16 Correct 852 ms 22268 KB Output is correct
17 Correct 1530 ms 17428 KB Output is correct
18 Correct 2412 ms 23096 KB Output is correct
19 Correct 1969 ms 23248 KB Output is correct
20 Correct 1789 ms 22652 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 8 ms 640 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 7 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 7 ms 640 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 1006 ms 35604 KB Output is correct
13 Correct 890 ms 35480 KB Output is correct
14 Correct 1129 ms 33224 KB Output is correct
15 Correct 1041 ms 32552 KB Output is correct
16 Correct 689 ms 21408 KB Output is correct
17 Correct 1061 ms 32936 KB Output is correct
18 Correct 994 ms 32420 KB Output is correct
19 Correct 1390 ms 19660 KB Output is correct
20 Correct 1752 ms 11000 KB Output is correct
21 Correct 665 ms 6008 KB Output is correct
22 Correct 1982 ms 15072 KB Output is correct
23 Correct 706 ms 22372 KB Output is correct
24 Correct 1244 ms 17636 KB Output is correct
25 Correct 2027 ms 23292 KB Output is correct
26 Correct 1819 ms 23200 KB Output is correct
27 Correct 1749 ms 22500 KB Output is correct
28 Correct 1236 ms 201936 KB Output is correct
29 Correct 2231 ms 216904 KB Output is correct
30 Correct 4232 ms 149980 KB Output is correct
31 Correct 4142 ms 121508 KB Output is correct
32 Correct 598 ms 10492 KB Output is correct
33 Correct 841 ms 13408 KB Output is correct
34 Correct 1410 ms 211036 KB Output is correct
35 Correct 1681 ms 114532 KB Output is correct
36 Correct 3294 ms 215024 KB Output is correct
37 Correct 2816 ms 215116 KB Output is correct
38 Correct 2725 ms 214476 KB Output is correct
39 Correct 2318 ms 171676 KB Output is correct
40 Correct 5 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 8 ms 640 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 7 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 7 ms 640 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 1034 ms 35584 KB Output is correct
13 Correct 868 ms 35464 KB Output is correct
14 Correct 1114 ms 32964 KB Output is correct
15 Correct 1060 ms 32516 KB Output is correct
16 Correct 717 ms 21600 KB Output is correct
17 Correct 1109 ms 32820 KB Output is correct
18 Correct 989 ms 32464 KB Output is correct
19 Correct 1390 ms 19576 KB Output is correct
20 Correct 1760 ms 10900 KB Output is correct
21 Correct 666 ms 6008 KB Output is correct
22 Correct 2013 ms 15028 KB Output is correct
23 Correct 706 ms 22296 KB Output is correct
24 Correct 1265 ms 17520 KB Output is correct
25 Correct 2012 ms 23184 KB Output is correct
26 Correct 1831 ms 23108 KB Output is correct
27 Correct 1690 ms 22676 KB Output is correct
28 Correct 1250 ms 201764 KB Output is correct
29 Correct 2213 ms 216776 KB Output is correct
30 Correct 4193 ms 150072 KB Output is correct
31 Correct 4099 ms 121420 KB Output is correct
32 Correct 614 ms 10580 KB Output is correct
33 Correct 819 ms 13284 KB Output is correct
34 Correct 1407 ms 211000 KB Output is correct
35 Correct 1734 ms 114500 KB Output is correct
36 Correct 3022 ms 215116 KB Output is correct
37 Correct 2576 ms 214984 KB Output is correct
38 Correct 2562 ms 214404 KB Output is correct
39 Runtime error 1074 ms 256008 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -