QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#191653 | #1429. Hit | Sorting | WA | 61ms | 14152kb | C++20 | 4.3kb | 2023-09-30 06:49:07 | 2023-09-30 06:49:07 |
Judging History
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