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
AC × 3
AC × 61
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