QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#191653#1429. HitSortingWA 61ms14152kbC++204.3kb2023-09-30 06:49:072023-09-30 06:49:07

Judging History

你现在查看的是最新测评结果

  • [2023-09-30 06:49:07]
  • 评测
  • 测评结果:WA
  • 用时:61ms
  • 内存:14152kb
  • [2023-09-30 06:49:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAXN = 1e5 + 7 ;
const int inf = 1e9 + 7 ;
const int LOG = 20 ;

int n ;
pii a[ MAXN ] ;


int mxcont ;
vector < int > act ;
bool used[ MAXN ] ;

void take_greedy ( ) {
    priority_queue < pii > st , en ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        used[ i ] = false ;
        st.push ( { -a[ i ].fi , i } ) ;
        en.push ( { -a[ i ].se , i } ) ;
    }
    act.clear ( ) ;
    while ( en.empty ( ) == false ) {
        int hh = -inf ;
        while ( en.empty ( ) == false ) {
            auto [ wh , id ] = en.top ( ) ;
            en.pop ( ) ;
            if ( used[ id ] == true ) { continue ; }
            hh = -wh ;
            break ;
        }
        if ( hh == -inf ) { break ; }
        act.push_back ( hh ) ;
        while ( st.empty ( ) == false ) {
            auto [ wh , id ] = st.top ( ) ;
            if ( -wh > hh ) { break ; }
            st.pop ( ) ;
            used[ id ] = true ;
        }
    }
    mxcont = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        int pos1 = lower_bound ( act.begin ( ) , act.end ( ) , a[ i ].fi ) - act.begin ( ) ;
        int pos2 = upper_bound ( act.begin ( ) , act.end ( ) , a[ i ].se ) - act.begin ( ) ;
        int aux = pos2 - pos1 ;
        mxcont = max ( mxcont , aux ) ;
    }
}

map < int , int > w ;
int rv[ 2 * MAXN ] ;
bool good[ 2 * MAXN ] ;

int lim[ 2 * MAXN ] ;
int nxt[ 2 * MAXN ][ LOG ] ;
vector < int > at_val[ 2 * MAXN ] ;
int mxpref[ 2 * MAXN ] ;
vector < int > ans ;

bool calc ( int sr ) {
    w.clear ( ) ;
    int tp = 0 ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        w[ a[ i ].fi ] = w[ a[ i ].se ] = 0 ;
    }
    for ( auto &e : w ) {
        e.se = ++ tp ;
        rv[ tp ] = e.fi ;
    }
    for ( int i = 0 ; i <= tp + 2 ; ++ i ) {
        at_val[ i ].clear ( ) ;
        good[ i ] = false ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        a[ i ].fi = w[ a[ i ].fi ] ;
        a[ i ].se = w[ a[ i ].se ] ;
        at_val[ a[ i ].fi ].push_back ( a[ i ].se ) ;
    }

    int mn = tp + 1 ;
    for ( int i = tp ; i >= 0 ; -- i ) {
        lim[ i ] = mn ;
        for ( auto en : at_val[ i ] ) {
            mn = min ( mn , en ) ;
        }
    }
    for ( int i = 1 ; i <= tp ; ++ i ) {
        mxpref[ i ] = mxpref[ i - 1 ] ;
        for ( auto x : at_val[ i ] ) {
            mxpref[ i ] = max ( mxpref[ i ] , x ) ;
        }
    }
    good[ tp + 1 ] = true ;
    for ( int i = 0 ; i < LOG ; ++ i ) { nxt[ tp + 1 ][ i ] = tp + 1 ; }
    deque < int > pts ;
    pts.push_back ( tp + 1 ) ;
    for ( int i = tp ; i >= 0 ; -- i ) {
        while ( pts.empty ( ) == false && pts.back ( ) > lim[ i ] ) { pts.pop_back ( ) ; }
        if ( pts.empty ( ) == true ) { return false ; }

        nxt[ i ][ 0 ] = pts.back ( ) ;
        for ( int j = 1 ; j < LOG ; ++ j ) {
            nxt[ i ][ j ] = nxt[ nxt[ i ][ j - 1 ] ][ j - 1 ] ;
        }
        int wh = i ;
        for ( int j = LOG - 1 ; j >= 0 ; -- j ) {
            if ( ( sr & ( 1 << j ) ) > 0 ) { wh = nxt[ wh ][ j ] ; }
        }
        if ( wh > mxpref[ i ] ) {
            good[ i ] = true ;
            pts.push_front ( i ) ;
        }
    }
    if ( good[ 0 ] == false ) { return false ; }
    int x = 0 ;
    ans.clear ( ) ;
    while ( nxt[ x ][ 0 ] <= tp ) {
        ans.push_back ( rv[ nxt[ x ][ 0 ] ] ) ;
        x = nxt[ x ][ 0 ] ;
    }
    return true ;
}

void solve ( ) {
    cin >> n ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ].fi >> a[ i ].se ;
    }
    take_greedy ( ) ;
    if ( calc ( mxcont - 1 ) == true ) {
        cout << mxcont - 1 << " " << ans.size ( ) << " " ;
        for ( auto x : ans ) {
            cout << x << " " ;
        }
        cout << "\n" ;
    }
    else {
        cout << mxcont << " " << act.size ( ) << " " ;
        for ( auto x : act ) {
            cout << x << " " ;
        }
        cout << "\n" ;
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; cin >> t ;
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 13936kb

input:

4
4
0 1
2 3
4 5
3 5
5
0 70
0 10
20 30
40 50
60 70
8
-1 7
-2 -1
-9 -7
-8 9
-9 -7
-2 4
-7 4
3 9
5
0 1
0 2
2 3
3 5
4 5

output:

1 3 1 2 5 
4 4 10 30 50 70 
2 3 -9 -1 9 
2 3 1 3 5 

result:

ok ok, tt = 4

Test #2:

score: 0
Accepted
time: 0ms
memory: 14032kb

input:

1
1
0 1

output:

1 1 1 

result:

ok ok, tt = 1

Test #3:

score: 0
Accepted
time: 2ms
memory: 10872kb

input:

3
1
-1000000000 1000000000
1
-1000000000 -999999999
1
999999999 1000000000

output:

1 1 1000000000 
1 1 -999999999 
1 1 1000000000 

result:

ok ok, tt = 3

Test #4:

score: 0
Accepted
time: 52ms
memory: 10624kb

input:

100000
1
-755794993 -744839313
1
638832683 645984490
1
333736843 342792055
1
-412526164 -400411740
1
193156287 205856204
1
266085745 268256106
1
789502967 806620391
1
85305828 86560242
1
-655573585 -644094805
1
517734490 518776542
1
-966001098 -958188900
1
-780504491 -762439365
1
-896592598 -8804653...

output:

1 1 -744839313 
1 1 645984490 
1 1 342792055 
1 1 -400411740 
1 1 205856204 
1 1 268256106 
1 1 806620391 
1 1 86560242 
1 1 -644094805 
1 1 518776542 
1 1 -958188900 
1 1 -762439365 
1 1 -880465378 
1 1 -545603970 
1 1 674193870 
1 1 -613177432 
1 1 -189815796 
1 1 -636284766 
1 1 -212256845 
1 1 -...

result:

ok ok, tt = 100000

Test #5:

score: 0
Accepted
time: 61ms
memory: 14040kb

input:

100000
1
-392749917 -319069731
1
761382535 804248178
1
-858764838 -819815600
1
-87503649 -20800126
1
-69252318 64456029
1
-848092983 -666742404
1
-659061625 -620054847
1
-982031817 -883932130
1
-47104919 97672798
1
-494834028 -456770262
1
496748206 692802903
1
572757539 669651153
1
-484466016 -41314...

output:

1 1 -319069731 
1 1 804248178 
1 1 -819815600 
1 1 -20800126 
1 1 64456029 
1 1 -666742404 
1 1 -620054847 
1 1 -883932130 
1 1 97672798 
1 1 -456770262 
1 1 692802903 
1 1 669651153 
1 1 -413146928 
1 1 912121104 
1 1 -402000624 
1 1 310772000 
1 1 -329279769 
1 1 888975125 
1 1 -505832802 
1 1 310...

result:

ok ok, tt = 100000

Test #6:

score: 0
Accepted
time: 55ms
memory: 10788kb

input:

100000
1
-422738609 -95619025
1
496655203 761501973
1
-253341552 895113150
1
-213934938 560617332
1
257193179 510136024
1
-684784337 -650911183
1
-999254900 62633326
1
-627557633 641989470
1
-682383675 66116491
1
-859630523 340664034
1
-422590930 433070710
1
259879968 316877801
1
-90014752 991378355...

output:

1 1 -95619025 
1 1 761501973 
1 1 895113150 
1 1 560617332 
1 1 510136024 
1 1 -650911183 
1 1 62633326 
1 1 641989470 
1 1 66116491 
1 1 340664034 
1 1 433070710 
1 1 316877801 
1 1 991378355 
1 1 351139472 
1 1 643790197 
1 1 899761936 
1 1 -713126923 
1 1 358738130 
1 1 502116510 
1 1 647513652 
...

result:

ok ok, tt = 100000

Test #7:

score: 0
Accepted
time: 55ms
memory: 12312kb

input:

100000
1
-146170891 -135832850
1
-758721094 -739814745
1
434418655 436843128
1
584625787 597671579
1
-54920782 -48746711
1
-890924962 -874340357
1
-955254050 -945006677
1
276114326 279390556
1
-291805472 -288200984
1
673823575 685514644
1
-43237398 -31640268
1
-239622315 -224829882
1
-596965402 -595...

output:

1 1 -135832850 
1 1 -739814745 
1 1 436843128 
1 1 597671579 
1 1 -48746711 
1 1 -874340357 
1 1 -945006677 
1 1 279390556 
1 1 -288200984 
1 1 685514644 
1 1 -31640268 
1 1 -224829882 
1 1 -595948258 
1 1 -886772435 
1 1 281278372 
1 1 -154122163 
1 1 302173751 
1 1 117393731 
1 1 -725867793 
1 1 -...

result:

ok ok, tt = 100000

Test #8:

score: 0
Accepted
time: 51ms
memory: 11872kb

input:

100000
1
-938525664 -817076126
1
-932701889 -823854498
1
-198817321 -90954343
1
852989237 895167117
1
-657597128 -592296022
1
-189337058 -60845257
1
-308394755 -143079067
1
-798793040 -658589397
1
587269730 632505978
1
463959892 651681553
1
210139744 354710208
1
-738322653 -579254528
1
-473167271 -4...

output:

1 1 -817076126 
1 1 -823854498 
1 1 -90954343 
1 1 895167117 
1 1 -592296022 
1 1 -60845257 
1 1 -143079067 
1 1 -658589397 
1 1 632505978 
1 1 651681553 
1 1 354710208 
1 1 -579254528 
1 1 -415805150 
1 1 -620402885 
1 1 -80905695 
1 1 866571582 
1 1 884604855 
1 1 888448333 
1 1 -97223882 
1 1 791...

result:

ok ok, tt = 100000

Test #9:

score: 0
Accepted
time: 57ms
memory: 14152kb

input:

100000
1
-124550996 175843021
1
-993480749 369513273
1
-472345946 866834459
1
51146719 619481540
1
-953985291 -388861986
1
30060232 86153621
1
397966610 670657620
1
228037899 527397835
1
-328812046 777147616
1
528770087 999819348
1
-443642177 430027557
1
-985366041 937429463
1
286165886 375753871
1
...

output:

1 1 175843021 
1 1 369513273 
1 1 866834459 
1 1 619481540 
1 1 -388861986 
1 1 86153621 
1 1 670657620 
1 1 527397835 
1 1 777147616 
1 1 999819348 
1 1 430027557 
1 1 937429463 
1 1 375753871 
1 1 -241036764 
1 1 253849507 
1 1 904700981 
1 1 875953108 
1 1 121979058 
1 1 465863397 
1 1 901461978 ...

result:

ok ok, tt = 100000

Test #10:

score: 0
Accepted
time: 36ms
memory: 10832kb

input:

18139
4
-336270587 -330557331
-252002330 -239258910
-186846904 -186440987
848243159 868102416
3
-195461235 -180651308
-250893512 -232183484
741194405 748153230
1
-583374820 -573301094
2
-289487516 -278362438
-617984192 -600701104
3
361103576 377771047
-629713150 -625261223
760487909 765234419
2
-789...

output:

1 4 -330557331 -239258910 -186440987 868102416 
1 3 -232183484 -180651308 748153230 
1 1 -573301094 
1 2 -600701104 -278362438 
1 3 -625261223 377771047 765234419 
1 2 -772865937 -84556628 
1 1 770021135 
1 4 -426773202 -230063854 446840121 522239063 
1 3 -817483854 -666548915 382548322 
1 6 -869109...

result:

ok ok, tt = 18139

Test #11:

score: -100
Wrong Answer
time: 50ms
memory: 12008kb

input:

18100
8
598403417 795720309
-373919856 -307381953
199626892 235156246
-217973856 -203235401
516184634 548146965
556458253 612829986
-686678416 -587302321
-251190508 -105682769
6
-526414856 -462880667
-734369052 -596753646
114814523 150451126
-10532542 21149560
-892168032 -828869761
-663573167 -62124...

output:

1 6 -587302321 -307381953 -203235401 235156246 548146965 612829986 
1 5 -828869761 -621240147 -462880667 21149560 150451126 
1 1 342776419 
1 5 -964969612 -855582387 -649355822 -35329612 188035491 
1 6 -798024093 -606741869 430693526 567632562 803810143 964101989 
1 3 -767627849 -495398605 400486568...

result:

wrong answer test 8630: expected 1, found 2