Submission #1230723
Source Code Expand
#include <bits/stdc++.h> #define xx first #define yy second #define mp make_pair #define pb push_back #define fill( x, y ) memset( x, y, sizeof x ) #define copy( x, y ) memcpy( x, y, sizeof x ) using namespace std; typedef long long LL; typedef pair < int, int > pa; inline int read() { int sc = 0; char ch = getchar(); while( ch < '0' || ch > '9' ) ch = getchar(); while( ch >= '0' && ch <= '9' ) sc = sc * 10 + ch - '0', ch = getchar(); return sc; } const int MAXN = 100010; const int INF = 1e9 + 7; int n, a[MAXN], b[MAXN], c[MAXN], d[MAXN], ans[MAXN], cur; bool usd[MAXN]; priority_queue < pa > q; vector < pa > v[MAXN]; int main() { #ifdef wxh010910 freopen( "data.in", "r", stdin ); #endif n = read(); for( int i = 1 ; i <= n ; i++ ) a[ i ] = read(), b[ i ] = read(); for( int i = 1 ; i <= n + 1 ; i++ ) c[ i ] = read(); int Q = read(); sort( c + 1, c + n + 2 ); for( int i = 1 ; i <= n ; i++ ) a[ i ] = lower_bound( c + 1, c + n + 2, a[ i ] ) - c, b[ i ] = lower_bound( c + 1, c + n + 2, b[ i ] ) - c; for( int i = 1 ; i <= n ; i++ ) d[ a[ i ] - 1 ]--, v[ a[ i ] - 1 ].pb( mp( -b[ i ], i ) ); d[ n + 2 ] = n; for( int i = n + 1 ; i ; i-- ) { for( auto y : v[ i ] ) q.push( y ); for( d[ i ] += d[ i + 1 ] ; d[ i ] - i < -1 ; q.pop() ) { if( q.empty() || -q.top().xx > i ) goto yjq; usd[ q.top().yy ] = 1; d[ i ]++; d[ -q.top().xx - 1 ]--; ans[ 0 ]++; } } fill( d, 0 ); while( !q.empty() ) q.pop(); for( int i = 1 ; i <= n ; i++ ) v[ i ].clear(); for( int i = 1 ; i <= n ; i++ ) { d[ usd[ i ] ? b[ i ] : a[ i ] ]++; if( !usd[ i ] ) v[ b[ i ] ].pb( mp( a[ i ] - 1, i ) ); } for( int i = 1 ; i <= n + 1 ; i++ ) { for( auto y : v[ i ] ) q.push( y ); d[ i ] += d[ i - 1 ]; ans[ i ] = ans[ i - 1 ]; if( d[ i ] - i == -1 && cur < i ) { if( q.empty() || q.top().xx < i ) ans[ i ] = INF; else cur = q.top().xx, q.pop(), ans[ i ]++; } } while( Q-- ) { int a = lower_bound( c + 1, c + n + 2, read() ) - c - 1, b = lower_bound( c + 1, c + n + 2, read() ) - c - 1, ret; ret = min( ans[ a ], ans[ b ] + 1 ); if( ret > n + 1 ) puts( "-1" ); else printf( "%d\n", n + 1 - ret ); } return 0; yjq:while( Q-- ) puts( "-1" ); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Two Faced Cards |
User | wxh010910 |
Language | C++14 (GCC 5.4.1) |
Score | 2000 |
Code Size | 2268 Byte |
Status | AC |
Exec Time | 128 ms |
Memory | 9460 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 2000 / 2000 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_49.txt, subtask_1_50.txt, subtask_1_51.txt, subtask_1_52.txt, subtask_1_53.txt, subtask_1_54.txt, subtask_1_55.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 3 ms | 4352 KB |
sample_02.txt | AC | 3 ms | 4352 KB |
sample_03.txt | AC | 3 ms | 4352 KB |
subtask_1_01.txt | AC | 54 ms | 6904 KB |
subtask_1_02.txt | AC | 60 ms | 6904 KB |
subtask_1_03.txt | AC | 30 ms | 5628 KB |
subtask_1_04.txt | AC | 52 ms | 7800 KB |
subtask_1_05.txt | AC | 39 ms | 5624 KB |
subtask_1_06.txt | AC | 84 ms | 7288 KB |
subtask_1_07.txt | AC | 56 ms | 7296 KB |
subtask_1_08.txt | AC | 77 ms | 7412 KB |
subtask_1_09.txt | AC | 80 ms | 8056 KB |
subtask_1_10.txt | AC | 46 ms | 6656 KB |
subtask_1_11.txt | AC | 30 ms | 5888 KB |
subtask_1_12.txt | AC | 44 ms | 5888 KB |
subtask_1_13.txt | AC | 62 ms | 6776 KB |
subtask_1_14.txt | AC | 35 ms | 6140 KB |
subtask_1_15.txt | AC | 43 ms | 6528 KB |
subtask_1_16.txt | AC | 27 ms | 4992 KB |
subtask_1_17.txt | AC | 118 ms | 9336 KB |
subtask_1_18.txt | AC | 28 ms | 6144 KB |
subtask_1_19.txt | AC | 36 ms | 6400 KB |
subtask_1_20.txt | AC | 89 ms | 7420 KB |
subtask_1_21.txt | AC | 128 ms | 8948 KB |
subtask_1_22.txt | AC | 118 ms | 9200 KB |
subtask_1_23.txt | AC | 128 ms | 8952 KB |
subtask_1_24.txt | AC | 118 ms | 9200 KB |
subtask_1_25.txt | AC | 126 ms | 9460 KB |
subtask_1_26.txt | AC | 118 ms | 8820 KB |
subtask_1_27.txt | AC | 60 ms | 7808 KB |
subtask_1_28.txt | AC | 117 ms | 8056 KB |
subtask_1_29.txt | AC | 125 ms | 9456 KB |
subtask_1_30.txt | AC | 119 ms | 8820 KB |
subtask_1_31.txt | AC | 59 ms | 7808 KB |
subtask_1_32.txt | AC | 122 ms | 8056 KB |
subtask_1_33.txt | AC | 125 ms | 9456 KB |
subtask_1_34.txt | AC | 118 ms | 8820 KB |
subtask_1_35.txt | AC | 60 ms | 7808 KB |
subtask_1_36.txt | AC | 118 ms | 8056 KB |
subtask_1_37.txt | AC | 125 ms | 9456 KB |
subtask_1_38.txt | AC | 117 ms | 8820 KB |
subtask_1_39.txt | AC | 59 ms | 7808 KB |
subtask_1_40.txt | AC | 121 ms | 8056 KB |
subtask_1_41.txt | AC | 111 ms | 8692 KB |
subtask_1_42.txt | AC | 110 ms | 8820 KB |
subtask_1_43.txt | AC | 106 ms | 8692 KB |
subtask_1_44.txt | AC | 104 ms | 8180 KB |
subtask_1_45.txt | AC | 46 ms | 6400 KB |
subtask_1_46.txt | AC | 95 ms | 8308 KB |
subtask_1_47.txt | AC | 95 ms | 8180 KB |
subtask_1_48.txt | AC | 95 ms | 8188 KB |
subtask_1_49.txt | AC | 95 ms | 8052 KB |
subtask_1_50.txt | AC | 41 ms | 6016 KB |
subtask_1_51.txt | AC | 3 ms | 4352 KB |
subtask_1_52.txt | AC | 3 ms | 4352 KB |
subtask_1_53.txt | AC | 3 ms | 4352 KB |
subtask_1_54.txt | AC | 3 ms | 4352 KB |
subtask_1_55.txt | AC | 3 ms | 4352 KB |