oj.uz

Submission #888935

# Submission time Handle Problem Language Result Execution time Memory
888935 2023-12-18T12:21:47 Z thunopro Passport (JOI23_passport) C++14
54 / 100
 832 ms 536948 KB 
#include<bits/stdc++.h>
using namespace std ;
#define maxn 200009 
#define ll long long
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1
#define right id<<1|1 
#define re exit(0); 

const int mod = 1e9+7 ; 
const int INF = 1e9 ; 
const int LOG = 18 ; 

typedef vector<int> vi ; 
typedef vector<ll> vl ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ; 
typedef pair<ll,ll> pll ;  

void add ( int &a , int b ) 
{
	a += b ; 
	if ( a < 0 ) a += mod ; 
	if ( a >= mod ) a -= mod ; 
}

template < typename T > void chkmin (T &a , T b) { if (a>b) a=b ;} 
template < typename T > void chkmax (T &a , T b) { if (a<b) a=b ;}

void rf () 
{
	freopen ("bai1.inp","r",stdin) ; 
//	freopen ("bai1.out","w",stdout) ; 
}

int n ; 
pii a [maxn] ; 

bool is_query [maxn] ;

void sub1 () 
{
	priority_queue <int> S ; 
	for ( int i = 1 ; i <= a [1].se ; i ++ ) S.push(a[i].se) ; 
	int res = 1 ; 
	int cur = a[1].se ; 
	while ( !S.empty () ) 
	{
		int u = S.top() ; S.pop() ; 
		if ( cur >= u ) break ; 
		while ( cur < u ) S . push (a[++cur].se) ; 
		res ++ ; 
	}
	if ( cur >= n ) cout << res ; 
	else cout << -1 ; 
} 

int dp [3009][3009] ; 
void sub2 () 
{
	int pos ; 
	for ( int i = 1 ; i <= n ; i ++ ) if ( is_query [i] ) pos = i ; 
	memset ( dp , 0x3f , sizeof dp ) ; 
	
	dp [pos][pos] = 0 ; 
	for ( int len = 0 ; len <= n-1 ; len ++ )
	{
		for ( int l = 1 ; l <= n ; l ++ ) 
		{
			int r = l + len ; 
			if ( r > n ) break ; 
			if ( dp [l][r] > 1e9 ) continue ; 
			for ( int i = l ; i <= r ; i ++ ) 
			{
				chkmin (dp[min(l,a[i].fi)][max(r,a[i].se)],dp[l][r]+1) ; 
			}
		}
	}

	if ( dp [1][n] > 1e9 ) dp [1][n] = - 1 ; 
	cout << dp [1][n] ; 
}

int range [3009][3009][2] ; 
void sub3 () 
{
	int pos ; 
	for ( int i = 1 ; i <= n ; i ++ ) if ( is_query [i] ) pos = i ; 
	memset ( dp , 0x3f , sizeof dp ) ; 
	dp [pos][pos] = 0 ; 
	
	deque <pii> q ; 
	q . push_back ({pos,pos}) ; 
	
	for ( int i = 1 ; i <= n ; i ++ ) for ( int j = i ; j <= n ; j ++ ) 
	{
		if ( i == j ) range [i][j][0] = INF , range [i][j][1] = - INF ; 
		
		if ( j > i ) range [i][j][0] = range [i][j-1][0] ; 
		chkmin (range[i][j][0],a[j].fi) ; 
		if ( j > i ) range [i][j][1] = range [i][j-1][1] ; 
		chkmax (range[i][j][1],a[j].se) ; 
	}
	
	while ( !q.empty() ) 
	{
		int l = q.front().fi , r = q.front().se ; 
		q.pop_front() ; 
		// state 1 : chosse left 
		int L = range [l][r][0] , R = r ; 
		if ( dp [L][R] > dp [l][r] + 1 ) q . push_back ({L,R}) , dp [L][R] = dp [l][r] + 1 ; 
		// state 2 : chosse right 
		L = l , R = range [l][r][1] ; 
		if ( dp [L][R] > dp [l][r] + 1 ) q . push_back ({L,R}) , dp [L][R] = dp [l][r] + 1 ; 
		// state 3 : in mid 
		if ( l == r ) 
		{
			L = a [l].fi , R = a[l].se ; 	
			if ( dp [L][R] > dp [l][r] + 1 ) q . push_back ({L,R}) , dp [L][R] = dp [l][r] + 1 ; 
		}
		else 
		{
			L = l + 1 , R = r ; 
			if ( dp [L][R] > dp [l][r]  ) q . push_front ({L,R}) , dp [L][R] = dp [l][r] ; 
			L = l , R = r - 1 ; 
			if ( dp [L][R] > dp [l][r]  ) q . push_front ({L,R}) , dp [L][R] = dp [l][r] ; 
		}
	}
	
	if ( dp [1][n] > INF ) dp [1][n] = - 1 ;
	cout << dp [1][n] ; 
}

struct shape {
	int l , r , w ; 
};
vector <shape> Edge [3009][3009] ; 

void sub4 () 
{
	for ( int i = 1 ; i <= n ; i ++ ) for ( int j = i ; j <= n ; j ++ ) 
	{
		if ( i == j ) range [i][j][0] = INF , range [i][j][1] = - INF ; 
		
		if ( j > i ) range [i][j][0] = range [i][j-1][0] ; 
		chkmin (range[i][j][0],a[j].fi) ; 
		if ( j > i ) range [i][j][1] = range [i][j-1][1] ; 
		chkmax (range[i][j][1],a[j].se) ; 
	}
	
	for ( int i = 1 ; i <= n ; i ++ ) 
	{
		for ( int j = i ; j <= n ; j ++ ) 
		{
			if ( i == j ) Edge [a[i].fi][a[i].se] . pb ({i,i,1}) ;
			else 
			{
				int L = range [i][j][0] , R = j ; 
				Edge [L][R] . pb ({i,j,1}) ; 
				L = i , R = range [i][j][1] ; 
				Edge [L][R] . pb ({i,j,1}) ;  
				L = i + 1 , R = j ; 
				if ( L >= 1 && R <= n ) Edge [L][R] . pb ({i,j,0}) ; 
				L = i , R = j - 1 ; 
				if ( L >= 1 && R <= n ) Edge [L][R] . pb ({i,j,0}) ;  
			} 
		}
	}
	
	memset ( dp , 0x3f , sizeof dp ) ; 
	deque <pii> q ; 
	q . push_back ({1,n}) ;
	dp [1][n] = 0 ; 
	while ( !q.empty () ) 
	{
		int l = q.front().fi , r = q.front().se ; q.pop_front() ; 

		for ( auto x : Edge [l][r] ) 
		{
			int L = x.l , R = x.r , w = x.w ; 
			if ( dp [L][R] > dp [l][r] + w ) 
			{
				dp [L][R] = dp [l][r] + w ; 
				if ( w == 0 ) q.push_front ({L,R}) ; 
				else q.push_back ({L,R}) ; 
			}
		}
	}
	
	for ( int i = 1 ; i <= n ; i ++ ) 
	{
		if ( is_query [i] ) 
		{
			if ( dp [i][i] > INF ) cout << -1 << "\n" ; 
			else cout << dp [i][i] << "\n" ; 
		}
	}
}
int main () 
{
	ios_base::sync_with_stdio(0) ; 
	cin.tie(0) ; cout.tie(0) ; 
//	rf () ; 
	
	cin >> n ; 
	for ( int i = 1 ; i <= n ; i ++ ) cin >> a [i].fi >> a[i].se ; 
	
	int nq ; cin >> nq ; 
	for ( int i = 1 ; i <= nq ; i ++ ) 
	{
		int x ; cin >> x ; 
		is_query [x] = true ; 
	}
	
	if ( nq == 1 && is_query [1] == true ) sub1 () ; 
	else if ( nq == 1 && n <= 300 ) sub2 () ;
	else if ( nq == 1 && n <= 2500 ) sub3 () ;  
	else if ( n <= 2500 ) sub4 () ; 
}

Compilation message

passport.cpp: In function 'void rf()':
passport.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
passport.cpp: In function 'void sub2()':
passport.cpp:67:16: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |  dp [pos][pos] = 0 ;
      |  ~~~~~~~~~~~~~~^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 215888 KB Output is correct
2 Correct 48 ms 215888 KB Output is correct
3 Correct 48 ms 215884 KB Output is correct
4 Correct 73 ms 217496 KB Output is correct
5 Correct 75 ms 217560 KB Output is correct
6 Correct 68 ms 216404 KB Output is correct
7 Correct 65 ms 217556 KB Output is correct
8 Correct 61 ms 216792 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 216064 KB Output is correct
2 Correct 52 ms 250948 KB Output is correct
3 Correct 45 ms 215896 KB Output is correct
4 Correct 46 ms 215892 KB Output is correct
5 Correct 50 ms 250704 KB Output is correct
6 Correct 51 ms 250708 KB Output is correct
7 Correct 51 ms 250704 KB Output is correct
8 Correct 52 ms 250940 KB Output is correct
9 Correct 51 ms 250880 KB Output is correct
10 Correct 51 ms 250704 KB Output is correct
11 Correct 51 ms 250736 KB Output is correct
12 Correct 52 ms 250960 KB Output is correct
13 Correct 53 ms 250760 KB Output is correct
14 Correct 52 ms 250948 KB Output is correct
15 Correct 51 ms 250960 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 216064 KB Output is correct
2 Correct 52 ms 250948 KB Output is correct
3 Correct 45 ms 215896 KB Output is correct
4 Correct 46 ms 215892 KB Output is correct
5 Correct 50 ms 250704 KB Output is correct
6 Correct 51 ms 250708 KB Output is correct
7 Correct 51 ms 250704 KB Output is correct
8 Correct 52 ms 250940 KB Output is correct
9 Correct 51 ms 250880 KB Output is correct
10 Correct 51 ms 250704 KB Output is correct
11 Correct 51 ms 250736 KB Output is correct
12 Correct 52 ms 250960 KB Output is correct
13 Correct 53 ms 250760 KB Output is correct
14 Correct 52 ms 250948 KB Output is correct
15 Correct 51 ms 250960 KB Output is correct
16 Correct 149 ms 306512 KB Output is correct
17 Correct 118 ms 310608 KB Output is correct
18 Correct 140 ms 310868 KB Output is correct
19 Correct 140 ms 308900 KB Output is correct
20 Correct 105 ms 310476 KB Output is correct
21 Correct 106 ms 310388 KB Output is correct
22 Correct 85 ms 310356 KB Output is correct
23 Correct 157 ms 315356 KB Output is correct
24 Correct 154 ms 310612 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 216064 KB Output is correct
2 Correct 52 ms 250948 KB Output is correct
3 Correct 45 ms 215896 KB Output is correct
4 Correct 46 ms 215892 KB Output is correct
5 Correct 50 ms 250704 KB Output is correct
6 Correct 51 ms 250708 KB Output is correct
7 Correct 51 ms 250704 KB Output is correct
8 Correct 52 ms 250940 KB Output is correct
9 Correct 51 ms 250880 KB Output is correct
10 Correct 51 ms 250704 KB Output is correct
11 Correct 51 ms 250736 KB Output is correct
12 Correct 52 ms 250960 KB Output is correct
13 Correct 53 ms 250760 KB Output is correct
14 Correct 52 ms 250948 KB Output is correct
15 Correct 51 ms 250960 KB Output is correct
16 Correct 149 ms 306512 KB Output is correct
17 Correct 118 ms 310608 KB Output is correct
18 Correct 140 ms 310868 KB Output is correct
19 Correct 140 ms 308900 KB Output is correct
20 Correct 105 ms 310476 KB Output is correct
21 Correct 106 ms 310388 KB Output is correct
22 Correct 85 ms 310356 KB Output is correct
23 Correct 157 ms 315356 KB Output is correct
24 Correct 154 ms 310612 KB Output is correct
25 Correct 55 ms 250972 KB Output is correct
26 Correct 50 ms 250948 KB Output is correct
27 Correct 547 ms 510420 KB Output is correct
28 Correct 832 ms 532664 KB Output is correct
29 Correct 738 ms 506164 KB Output is correct
30 Correct 606 ms 536948 KB Output is correct
31 Correct 551 ms 510984 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 215888 KB Output is correct
2 Correct 48 ms 215888 KB Output is correct
3 Correct 48 ms 215884 KB Output is correct
4 Correct 73 ms 217496 KB Output is correct
5 Correct 75 ms 217560 KB Output is correct
6 Correct 68 ms 216404 KB Output is correct
7 Correct 65 ms 217556 KB Output is correct
8 Correct 61 ms 216792 KB Output is correct
9 Correct 45 ms 216064 KB Output is correct
10 Correct 52 ms 250948 KB Output is correct
11 Correct 45 ms 215896 KB Output is correct
12 Correct 46 ms 215892 KB Output is correct
13 Correct 50 ms 250704 KB Output is correct
14 Correct 51 ms 250708 KB Output is correct
15 Correct 51 ms 250704 KB Output is correct
16 Correct 52 ms 250940 KB Output is correct
17 Correct 51 ms 250880 KB Output is correct
18 Correct 51 ms 250704 KB Output is correct
19 Correct 51 ms 250736 KB Output is correct
20 Correct 52 ms 250960 KB Output is correct
21 Correct 53 ms 250760 KB Output is correct
22 Correct 52 ms 250948 KB Output is correct
23 Correct 51 ms 250960 KB Output is correct
24 Correct 149 ms 306512 KB Output is correct
25 Correct 118 ms 310608 KB Output is correct
26 Correct 140 ms 310868 KB Output is correct
27 Correct 140 ms 308900 KB Output is correct
28 Correct 105 ms 310476 KB Output is correct
29 Correct 106 ms 310388 KB Output is correct
30 Correct 85 ms 310356 KB Output is correct
31 Correct 157 ms 315356 KB Output is correct
32 Correct 154 ms 310612 KB Output is correct
33 Correct 55 ms 250972 KB Output is correct
34 Correct 50 ms 250948 KB Output is correct
35 Correct 547 ms 510420 KB Output is correct
36 Correct 832 ms 532664 KB Output is correct
37 Correct 738 ms 506164 KB Output is correct
38 Correct 606 ms 536948 KB Output is correct
39 Correct 551 ms 510984 KB Output is correct
40 Incorrect 79 ms 216404 KB Output isn't correct
41 Halted 0 ms 0 KB -