oj.uz

답안 #295279

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
295279 2020-09-09T14:58:17 Z CaroLinda 새 집 (APIO18_new_home) C++17
80 / 100
 5000 ms 774528 KB 
#include <bits/stdc++.h>

#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,fma,tune=native")
#pragma GCC optimize("unroll-loops")

#define lp(i,a,b) for(int i = a; i < b; i++)
#define pb push_back
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define debug printf
#define tiii tuple<int,int,int>
#define mkt make_tuple
#define pii pair<int,int>
#define mk make_pair
#define ll long long
#define ff first
#define ss second

const int MAXN = 3e5+10 ;
const int MAXT = 1e9+10 ;
const int MAX_COORD = 1e9+7 ;

using namespace std ;

struct Event
{
    int xConta, xIntercept, type , t1, t2 ;
    Event(int a=0, int b=0, int c=0, int d=0, int e=0) : xConta(a), xIntercept(b), type(c) , t1(d), t2(e){}

};

int ansQuery[MAXN] ;

struct Seg
{

    int n ;
    vector<Event> tree[MAXN*2] ;

    int m(int l, int r) { return (l+r)>>1 ; }

    void insertEvent(int t1, int t2,  Event e)
    {

        if(e.type > 0)
        {
            for(t1 += n ; t1 >= 1 ; t1 >>= 1)
                tree[t1].pb(e) ;

            return ;
        }

        for(t1 += n , t2 += n ; t1 < t2 ; t1 >>= 1 , t2>>=1 )
        {
            if( t1&1 ) tree[t1].pb(e), t1++ ;
            if( t2&1 ) t2--, tree[t2].pb(e) ;
        }

    }

    void solve(int forbiddenType )
    {
        for(int i = 1 ; i < 2*n ; i++ )
        {
            int mxNegative = -MAXT , mnPositive = MAXT ;

            for(auto e : tree[i])
            {
                if( e.type == forbiddenType ) continue ;
                if( e.type > 0 )
                {
                    ansQuery[ e.type ] = max( ansQuery[e.type] , (forbiddenType == 0) ? mxNegative - e.xConta : e.xConta-mnPositive ) ;
                }
                else
                {
                    if(forbiddenType == 0) mxNegative = max(mxNegative, e.xIntercept ) ;
                    else mnPositive = min(mnPositive, e.xIntercept ) ;
                }
            }
        }
    }

} seg ;

//O ANO PODE IR ATÉ 10^8
//VAI TER QUE FAZER COMPRESSÃO

int N , K , Q ;
int timeRight[MAXN] , timeLeft[MAXN] , midRight[MAXN] ,midLeft[MAXN] ;
vector<int> compressionTime , compressionX ;
set<int> lojinhas ;
vector< pii > myVecOfPairs ;
vector<pii> coordX[MAXN] ;
vector<tiii> myStores[MAXN] ;
map< pii , int > segments[MAXN] ;
vector<Event> sweep ;

int maiorIgual(int x)
{

    int l = 0 , r = sz(compressionTime) - 1 , mid , best = r+1 ;

    while( l <= r )
    {
        mid = (l+r)>>1 ;
        if(compressionTime[mid] >= x)
        {
            best = mid ;
            r = mid - 1 ;
        }
        else l = mid + 1 ;
    }
    return best ;
}
int menorIgual(int x)
{
    int l = 0 , r = sz(compressionTime)-1 , mid , best = -1 ;

    while(l <= r)
    {
        mid = (l+r)>>1 ;
        if(compressionTime[mid] <= x )
        {
            best = mid ;
            l = mid + 1 ;
        }
        else r = mid - 1 ;
    }

    return best ;
}

void coloca(set<int>::iterator l , set<int>::iterator r , int t )
{

    int xl = compressionX[*l] ;
    int xr = compressionX[*r] ;

    midRight[*l] = (xr - xl)>>1 ;
    midRight[*l] += xl ;
    midLeft[*r] = ( (xr-xl)%2 == 0 ) ? midRight[*l] : ( midRight[*l]+1);

    timeRight[*l] = t ;
    timeLeft[*r] = t ;

}

void apaga( set<int>::iterator l , set<int>::iterator r , int t )
{

    int xl = compressionX[*l] ;
    int xr = compressionX[*r] ;

    if(timeRight[*l] <= t )
        sweep.pb( Event( midRight[*l] , xl , 0 , timeRight[*l] , t ) ) ;

    if(timeLeft[*r] <= t)
        sweep.pb( Event( midLeft[*r] , xr , -1, timeLeft[*r] , t ) ) ;

}


int main()
{

    scanf("%d%d%d", &N , &K , &Q ) ;

    for(int i = 1 , x , t , a , b ; i <= N ; i++ )
    {
        scanf("%d%d%d%d", &x, &t, &a, &b ) ;
        myStores[t].pb( mkt(x,a,b) ) ;
        compressionX.pb(x) ;
    }

    compressionX.pb(-MAXT) ;
    compressionX.pb(MAXT);
    sort(all(compressionX));
    compressionX.erase( unique( all(compressionX) ) , compressionX.end() ) ;

    for(int i = 1 ; i <= K ; i++ )
    {

        sort(all(myStores[i])) ;

        for(auto &tup : myStores[i])
        {
            int l = 0 , r = sz(compressionX) - 1 , mid ;

            while(l <= r)
            {
                mid = (l+r)>>1 ;

                if( compressionX[mid] == get<0>(tup) ) break ;
                else if( compressionX[mid] < get<0>(tup) ) l =mid+1 ;
                else r = mid - 1 ;
            }

            get<0>(tup) = mid ;
            coordX[mid].pb( mk(get<1>(tup) , get<2>(tup)) ) ;
        }

       for(int j = 0 ; j < sz(myStores[i]) ; j++ )
        {

            int X = get<0>(myStores[i][j]) ;

            if(j != 0 && X == get<0>(myStores[i][j-1]) ) continue ;

            int mnTime =  coordX[ X ][0].ff ;
            int mxTime =  coordX[ X ][0].ss ;
            coordX[X].pb( mk(MAXT, MAXT) ) ;

            for(int g = 1 ; g < sz( coordX[ X ] ) ; g++ )
            {
                if( coordX[X][g].ff > mxTime )
                {
                    myVecOfPairs.pb( mk( mnTime , -X ) ) ;
                    myVecOfPairs.pb( mk( mxTime , X ) ) ;

                    mnTime = coordX[X][g].ff ;
                    mxTime = coordX[X][g].ss ;
                }
                else mxTime = max(mxTime, coordX[X][g].ss ) ;
            }

            coordX[X].clear() ;

        }

        //Cada x eh unico e ta comprimido, pode ser o id dele

        sort(all(myVecOfPairs)) ;

        lojinhas.insert(0) ;
        lojinhas.insert( sz(compressionX) - 1 ) ;

        coloca( lojinhas.begin() , prev( lojinhas.end() ) , 1 ) ;

        for(auto e : myVecOfPairs )
        {
            int t = e.ff ;
            int x = e.ss ;

            set<int>::iterator itMore , itLess;

            if(x < 0)
            {
                itMore = lojinhas.upper_bound(-x) ;
                itLess = itMore , itLess-- ;

                apaga(itLess, itMore, t-1) ;

                lojinhas.insert(-x) ;

                itMore = lojinhas.find(-x) ;
                itLess = itMore , itLess-- ;

                coloca(itLess, itMore , t) ;

                itLess = itMore , itLess++ ;
                swap(itLess, itMore) ;

                coloca(itLess, itMore, t) ;

            }
            else
            {
                itMore = lojinhas.find(x) ;
                itLess = itMore , itLess-- ;

                apaga(itLess, itMore , t ) ;


                itLess = itMore , itLess++ ;
                swap(itLess, itMore ) ;

                apaga(itLess, itMore, t ) ;

                lojinhas.erase(itLess) ;

                itMore = lojinhas.upper_bound(x) ;
                itLess = itMore , itLess-- ;

                coloca(itLess, itMore, t+1 ) ;

            }

        }

        apaga( lojinhas.begin() , prev(lojinhas.end() ) , MAXT ) ;

        myVecOfPairs.clear() ;
        lojinhas.clear() ;

    }

   // for(auto e : sweep ) debug("%d %d %d %d %d\n", e.xConta, e.xIntercept, e.type , e.t1, e.t2 ) ;

    for(int i = 1 , l , y ; i <= Q ; i++ )
    {
        scanf("%d%d", &l, &y ) ;
        sweep.pb( Event(l,l,i,y,y) );
        compressionTime.pb(y) ;
    }

    //Indeed, compression time!
    sort(all(compressionTime)) ;
    compressionTime.erase( unique(all(compressionTime)) , compressionTime.end() );
    //

    sort(all(sweep), [&](Event a, Event b)
         {
             if( a.xConta != b.xConta ) return a.xConta < b.xConta ;
             else return a.type < b.type ;
         } );

    for(auto &e : sweep ) e.t1 = maiorIgual(e.t1) , e.t2 = menorIgual(e.t2) ;
   // for(auto e : sweep ) printf("coord %d %d, e tempo %d %d e tipo %d\n" , e.xConta, e.xIntercept, e.t1, e.t2, e.type ) ;

    seg.n = sz(compressionTime) ;

    for(auto e : sweep )
        if( e.type != 0 && e.t1 <= e.t2 )
            seg.insertEvent( e.t1, e.t2+1 , e ) ;

    seg.solve( 0 ) ;

    sort(all(sweep), [&](Event a, Event b)
     {
         if( a.xConta != b.xConta ) return a.xConta > b.xConta ;
         else return a.type < b.type ;
     } );

    for(int i = 1 ; i < 2*seg.n ; i++ ) seg.tree[i].clear() ;

    for(auto e : sweep )
        if(e.type != -1 && e.t1 <= e.t2 )
            seg.insertEvent( e.t1, e.t2+1, e ) ;

    seg.solve( -1 ) ;

    for(int i = 1 ; i <= Q ; i++ ) printf("%d\n" , ansQuery[i] > 100000000 ? -1 : ansQuery[i] ) ;

}

/*
2 1 1
39682063 1 1 100000000
29000832 1 1 100000000
34341447 100000000

2 1 1
39682063 1 1 100000000
29000832 1 1 100000000
34341447 100000000

5 4 1
39682063 3 1 100000000
37986244 2 1 100000000
29273266 1 1 100000000
33173370 4 1 100000000
29000832 3 1 100000000
34341447 100000000



5 2 2
4 2 3 3
5 1 2 5
5 1 2 5
5 1 5 5
4 1 3 3
90 3
7 10

1 1 1
5 1 1 10
7 5

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

6 3 4
10 1 1 100000000
13 2 1 100000000
10 2 1 100000000
1 3 1 100000000
15 1 1 100000000
26 3 1 100000000
15 20
30 100000000
50 800
100000000 1

4 2 4
3 1 1 10
4 1 8 10
9 2 2 4
7 2 5 7
5 3
5 6
5 9
1 10

1 1 1
100000000 1 1 1 1
1 1

*/

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:168:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  168 |     scanf("%d%d%d", &N , &K , &Q ) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:172:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  172 |         scanf("%d%d%d%d", &x, &t, &a, &b ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:303:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  303 |         scanf("%d%d", &l, &y ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~
new_home.cpp:189:52: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
  189 |             int l = 0 , r = sz(compressionX) - 1 , mid ;
      |                                                    ^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 42624 KB Output is correct
2 Correct 29 ms 42616 KB Output is correct
3 Correct 29 ms 42624 KB Output is correct
4 Correct 29 ms 42656 KB Output is correct
5 Correct 29 ms 42744 KB Output is correct
6 Correct 32 ms 43008 KB Output is correct
7 Correct 31 ms 43128 KB Output is correct
8 Correct 33 ms 43032 KB Output is correct
9 Correct 31 ms 43128 KB Output is correct
10 Correct 33 ms 43008 KB Output is correct
11 Correct 32 ms 42872 KB Output is correct
12 Correct 33 ms 42880 KB Output is correct
13 Correct 33 ms 42880 KB Output is correct
14 Correct 30 ms 42880 KB Output is correct
15 Correct 37 ms 43000 KB Output is correct
16 Correct 31 ms 43008 KB Output is correct
17 Correct 34 ms 43000 KB Output is correct
18 Correct 36 ms 43008 KB Output is correct
19 Correct 31 ms 43000 KB Output is correct
20 Correct 31 ms 43008 KB Output is correct
21 Correct 29 ms 42752 KB Output is correct
22 Correct 31 ms 43128 KB Output is correct
23 Correct 32 ms 43136 KB Output is correct
24 Correct 32 ms 43000 KB Output is correct
25 Correct 32 ms 43056 KB Output is correct
26 Correct 33 ms 42880 KB Output is correct
27 Correct 33 ms 42928 KB Output is correct
28 Correct 32 ms 42964 KB Output is correct
29 Correct 33 ms 42872 KB Output is correct
30 Correct 31 ms 42880 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 42624 KB Output is correct
2 Correct 29 ms 42616 KB Output is correct
3 Correct 29 ms 42624 KB Output is correct
4 Correct 29 ms 42656 KB Output is correct
5 Correct 29 ms 42744 KB Output is correct
6 Correct 32 ms 43008 KB Output is correct
7 Correct 31 ms 43128 KB Output is correct
8 Correct 33 ms 43032 KB Output is correct
9 Correct 31 ms 43128 KB Output is correct
10 Correct 33 ms 43008 KB Output is correct
11 Correct 32 ms 42872 KB Output is correct
12 Correct 33 ms 42880 KB Output is correct
13 Correct 33 ms 42880 KB Output is correct
14 Correct 30 ms 42880 KB Output is correct
15 Correct 37 ms 43000 KB Output is correct
16 Correct 31 ms 43008 KB Output is correct
17 Correct 34 ms 43000 KB Output is correct
18 Correct 36 ms 43008 KB Output is correct
19 Correct 31 ms 43000 KB Output is correct
20 Correct 31 ms 43008 KB Output is correct
21 Correct 29 ms 42752 KB Output is correct
22 Correct 31 ms 43128 KB Output is correct
23 Correct 32 ms 43136 KB Output is correct
24 Correct 32 ms 43000 KB Output is correct
25 Correct 32 ms 43056 KB Output is correct
26 Correct 33 ms 42880 KB Output is correct
27 Correct 33 ms 42928 KB Output is correct
28 Correct 32 ms 42964 KB Output is correct
29 Correct 33 ms 42872 KB Output is correct
30 Correct 31 ms 42880 KB Output is correct
31 Correct 784 ms 140544 KB Output is correct
32 Correct 113 ms 52768 KB Output is correct
33 Correct 796 ms 134124 KB Output is correct
34 Correct 772 ms 134356 KB Output is correct
35 Correct 796 ms 139892 KB Output is correct
36 Correct 788 ms 139628 KB Output is correct
37 Correct 620 ms 124488 KB Output is correct
38 Correct 620 ms 124468 KB Output is correct
39 Correct 485 ms 109892 KB Output is correct
40 Correct 523 ms 113852 KB Output is correct
41 Correct 708 ms 120540 KB Output is correct
42 Correct 720 ms 121444 KB Output is correct
43 Correct 101 ms 49276 KB Output is correct
44 Correct 690 ms 120688 KB Output is correct
45 Correct 640 ms 111444 KB Output is correct
46 Correct 570 ms 96076 KB Output is correct
47 Correct 399 ms 94572 KB Output is correct
48 Correct 376 ms 90292 KB Output is correct
49 Correct 435 ms 100812 KB Output is correct
50 Correct 508 ms 118568 KB Output is correct
51 Correct 442 ms 96240 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2326 ms 393968 KB Output is correct
2 Correct 2206 ms 373940 KB Output is correct
3 Correct 2867 ms 573128 KB Output is correct
4 Correct 2456 ms 426120 KB Output is correct
5 Correct 2217 ms 386528 KB Output is correct
6 Correct 2159 ms 381716 KB Output is correct
7 Correct 2697 ms 583392 KB Output is correct
8 Correct 2377 ms 423128 KB Output is correct
9 Correct 2256 ms 376256 KB Output is correct
10 Correct 2204 ms 365616 KB Output is correct
11 Correct 1554 ms 347556 KB Output is correct
12 Correct 1696 ms 384432 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3623 ms 488968 KB Output is correct
2 Correct 426 ms 95816 KB Output is correct
3 Correct 3594 ms 486536 KB Output is correct
4 Correct 4190 ms 679560 KB Output is correct
5 Correct 3706 ms 502984 KB Output is correct
6 Correct 3751 ms 534188 KB Output is correct
7 Correct 3604 ms 466392 KB Output is correct
8 Correct 3524 ms 477776 KB Output is correct
9 Correct 3823 ms 696556 KB Output is correct
10 Correct 3505 ms 524684 KB Output is correct
11 Correct 3559 ms 503384 KB Output is correct
12 Correct 3568 ms 469164 KB Output is correct
13 Correct 2067 ms 438140 KB Output is correct
14 Correct 2019 ms 433772 KB Output is correct
15 Correct 2303 ms 449524 KB Output is correct
16 Correct 2521 ms 457992 KB Output is correct
17 Correct 2430 ms 448212 KB Output is correct

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 42624 KB Output is correct
2 Correct 29 ms 42616 KB Output is correct
3 Correct 29 ms 42624 KB Output is correct
4 Correct 29 ms 42656 KB Output is correct
5 Correct 29 ms 42744 KB Output is correct
6 Correct 32 ms 43008 KB Output is correct
7 Correct 31 ms 43128 KB Output is correct
8 Correct 33 ms 43032 KB Output is correct
9 Correct 31 ms 43128 KB Output is correct
10 Correct 33 ms 43008 KB Output is correct
11 Correct 32 ms 42872 KB Output is correct
12 Correct 33 ms 42880 KB Output is correct
13 Correct 33 ms 42880 KB Output is correct
14 Correct 30 ms 42880 KB Output is correct
15 Correct 37 ms 43000 KB Output is correct
16 Correct 31 ms 43008 KB Output is correct
17 Correct 34 ms 43000 KB Output is correct
18 Correct 36 ms 43008 KB Output is correct
19 Correct 31 ms 43000 KB Output is correct
20 Correct 31 ms 43008 KB Output is correct
21 Correct 29 ms 42752 KB Output is correct
22 Correct 31 ms 43128 KB Output is correct
23 Correct 32 ms 43136 KB Output is correct
24 Correct 32 ms 43000 KB Output is correct
25 Correct 32 ms 43056 KB Output is correct
26 Correct 33 ms 42880 KB Output is correct
27 Correct 33 ms 42928 KB Output is correct
28 Correct 32 ms 42964 KB Output is correct
29 Correct 33 ms 42872 KB Output is correct
30 Correct 31 ms 42880 KB Output is correct
31 Correct 784 ms 140544 KB Output is correct
32 Correct 113 ms 52768 KB Output is correct
33 Correct 796 ms 134124 KB Output is correct
34 Correct 772 ms 134356 KB Output is correct
35 Correct 796 ms 139892 KB Output is correct
36 Correct 788 ms 139628 KB Output is correct
37 Correct 620 ms 124488 KB Output is correct
38 Correct 620 ms 124468 KB Output is correct
39 Correct 485 ms 109892 KB Output is correct
40 Correct 523 ms 113852 KB Output is correct
41 Correct 708 ms 120540 KB Output is correct
42 Correct 720 ms 121444 KB Output is correct
43 Correct 101 ms 49276 KB Output is correct
44 Correct 690 ms 120688 KB Output is correct
45 Correct 640 ms 111444 KB Output is correct
46 Correct 570 ms 96076 KB Output is correct
47 Correct 399 ms 94572 KB Output is correct
48 Correct 376 ms 90292 KB Output is correct
49 Correct 435 ms 100812 KB Output is correct
50 Correct 508 ms 118568 KB Output is correct
51 Correct 442 ms 96240 KB Output is correct
52 Correct 831 ms 170068 KB Output is correct
53 Correct 883 ms 159064 KB Output is correct
54 Correct 836 ms 150124 KB Output is correct
55 Correct 695 ms 133252 KB Output is correct
56 Correct 669 ms 137068 KB Output is correct
57 Correct 694 ms 124376 KB Output is correct
58 Correct 738 ms 138332 KB Output is correct
59 Correct 765 ms 146124 KB Output is correct
60 Correct 805 ms 127192 KB Output is correct
61 Correct 187 ms 64364 KB Output is correct
62 Correct 804 ms 165204 KB Output is correct
63 Correct 773 ms 156780 KB Output is correct
64 Correct 761 ms 153184 KB Output is correct
65 Correct 732 ms 143584 KB Output is correct
66 Correct 719 ms 127448 KB Output is correct
67 Correct 239 ms 74320 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 42624 KB Output is correct
2 Correct 29 ms 42616 KB Output is correct
3 Correct 29 ms 42624 KB Output is correct
4 Correct 29 ms 42656 KB Output is correct
5 Correct 29 ms 42744 KB Output is correct
6 Correct 32 ms 43008 KB Output is correct
7 Correct 31 ms 43128 KB Output is correct
8 Correct 33 ms 43032 KB Output is correct
9 Correct 31 ms 43128 KB Output is correct
10 Correct 33 ms 43008 KB Output is correct
11 Correct 32 ms 42872 KB Output is correct
12 Correct 33 ms 42880 KB Output is correct
13 Correct 33 ms 42880 KB Output is correct
14 Correct 30 ms 42880 KB Output is correct
15 Correct 37 ms 43000 KB Output is correct
16 Correct 31 ms 43008 KB Output is correct
17 Correct 34 ms 43000 KB Output is correct
18 Correct 36 ms 43008 KB Output is correct
19 Correct 31 ms 43000 KB Output is correct
20 Correct 31 ms 43008 KB Output is correct
21 Correct 29 ms 42752 KB Output is correct
22 Correct 31 ms 43128 KB Output is correct
23 Correct 32 ms 43136 KB Output is correct
24 Correct 32 ms 43000 KB Output is correct
25 Correct 32 ms 43056 KB Output is correct
26 Correct 33 ms 42880 KB Output is correct
27 Correct 33 ms 42928 KB Output is correct
28 Correct 32 ms 42964 KB Output is correct
29 Correct 33 ms 42872 KB Output is correct
30 Correct 31 ms 42880 KB Output is correct
31 Correct 784 ms 140544 KB Output is correct
32 Correct 113 ms 52768 KB Output is correct
33 Correct 796 ms 134124 KB Output is correct
34 Correct 772 ms 134356 KB Output is correct
35 Correct 796 ms 139892 KB Output is correct
36 Correct 788 ms 139628 KB Output is correct
37 Correct 620 ms 124488 KB Output is correct
38 Correct 620 ms 124468 KB Output is correct
39 Correct 485 ms 109892 KB Output is correct
40 Correct 523 ms 113852 KB Output is correct
41 Correct 708 ms 120540 KB Output is correct
42 Correct 720 ms 121444 KB Output is correct
43 Correct 101 ms 49276 KB Output is correct
44 Correct 690 ms 120688 KB Output is correct
45 Correct 640 ms 111444 KB Output is correct
46 Correct 570 ms 96076 KB Output is correct
47 Correct 399 ms 94572 KB Output is correct
48 Correct 376 ms 90292 KB Output is correct
49 Correct 435 ms 100812 KB Output is correct
50 Correct 508 ms 118568 KB Output is correct
51 Correct 442 ms 96240 KB Output is correct
52 Correct 2326 ms 393968 KB Output is correct
53 Correct 2206 ms 373940 KB Output is correct
54 Correct 2867 ms 573128 KB Output is correct
55 Correct 2456 ms 426120 KB Output is correct
56 Correct 2217 ms 386528 KB Output is correct
57 Correct 2159 ms 381716 KB Output is correct
58 Correct 2697 ms 583392 KB Output is correct
59 Correct 2377 ms 423128 KB Output is correct
60 Correct 2256 ms 376256 KB Output is correct
61 Correct 2204 ms 365616 KB Output is correct
62 Correct 1554 ms 347556 KB Output is correct
63 Correct 1696 ms 384432 KB Output is correct
64 Correct 3623 ms 488968 KB Output is correct
65 Correct 426 ms 95816 KB Output is correct
66 Correct 3594 ms 486536 KB Output is correct
67 Correct 4190 ms 679560 KB Output is correct
68 Correct 3706 ms 502984 KB Output is correct
69 Correct 3751 ms 534188 KB Output is correct
70 Correct 3604 ms 466392 KB Output is correct
71 Correct 3524 ms 477776 KB Output is correct
72 Correct 3823 ms 696556 KB Output is correct
73 Correct 3505 ms 524684 KB Output is correct
74 Correct 3559 ms 503384 KB Output is correct
75 Correct 3568 ms 469164 KB Output is correct
76 Correct 2067 ms 438140 KB Output is correct
77 Correct 2019 ms 433772 KB Output is correct
78 Correct 2303 ms 449524 KB Output is correct
79 Correct 2521 ms 457992 KB Output is correct
80 Correct 2430 ms 448212 KB Output is correct
81 Correct 831 ms 170068 KB Output is correct
82 Correct 883 ms 159064 KB Output is correct
83 Correct 836 ms 150124 KB Output is correct
84 Correct 695 ms 133252 KB Output is correct
85 Correct 669 ms 137068 KB Output is correct
86 Correct 694 ms 124376 KB Output is correct
87 Correct 738 ms 138332 KB Output is correct
88 Correct 765 ms 146124 KB Output is correct
89 Correct 805 ms 127192 KB Output is correct
90 Correct 187 ms 64364 KB Output is correct
91 Correct 804 ms 165204 KB Output is correct
92 Correct 773 ms 156780 KB Output is correct
93 Correct 761 ms 153184 KB Output is correct
94 Correct 732 ms 143584 KB Output is correct
95 Correct 719 ms 127448 KB Output is correct
96 Correct 239 ms 74320 KB Output is correct
97 Execution timed out 5103 ms 774528 KB Time limit exceeded
98 Halted 0 ms 0 KB -