제출 #895138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895138		thunopro	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	121 ms	26636 KiB

event2

#include<bits/stdc++.h>
using namespace std ; 
#define maxn 300009 
#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);
#define _lower(v,x) lower_bound(v.begin(),v.end(),x)-v.begin()+1

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

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

void add ( int&a , int b ) { if ((a+=b) > mod ) a -= mod ; } 
void sub ( int&a , int b ) { if ((a-=b) < 0 ) a += mod ; } 
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

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

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ; 
	int res = _pow ( a , n / 2 ) ; 
	if ( n % 2 ) return ( 1ll * res * res % mod * a % mod ) ; 
	else return ( 1ll * res * res % mod ) ; 
}

// fill order 
// check find order by build 
// build count (l,r) = spar
// find left and right by set
 
int n , k ; 
struct line {
	int l , r ; 
} a [maxn] ;

void mapping () 
{
	vi v ; 
	for ( int i = 1 ; i <= n ; i ++ ) v . pb (a[i].l) , v . pb (a[i].r) ;
	sort (v.begin(),v.end()) ; 
	v.resize (unique(v.begin(),v.end())-v.begin()) ; 
	for ( int i = 1 ; i <= n ; i ++ ) a [i].l = _lower(v,a[i].l) , a [i].r = _lower(v,a[i].r) ; 
}

const int N = 2e5 ;
const int maxN = N + 9 ; 

int Min [maxN] ; 
int par [maxN][20] ; 
void build_count () 
{
	memset ( Min , 0x3f , sizeof Min ) ;
	memset ( par , 0x3f , sizeof par ) ;  
	for ( int i = 1 ; i <= N ; i ++ ) chkmin (Min[a[i].l],a[i].r) ; 
	for ( int i = N ; i >= 1 ; i -- ) 
	{
		par [i][0] = Min[i] ; 
		chkmin (par[i][0],par[i+1][0]) ; 
	}
	for ( int j = 1 ; j <= __lg (N) ; j ++ ) 
	{
		for ( int i = 1 ; i <= N-(1<<j)+1 ; i ++ ) 
		{
			if ( par[i][j-1] <= N ) par [i][j] = par[par[i][j-1]][j-1] ; 
		}
	}
}
int count_range ( int l , int r ) 
{
	int res = 0 ; 
	for ( int i = LOG ; i >= 0 ; i -- ) 
	{
		if ( par[l][i] <= r ) 
		{
			res += (1<<i) ; 
			l = par[l][i] ; 
		}
	}
	return res ; 
}
int main ( ) 
{
	ios_base :: sync_with_stdio (0) ; 
	cin.tie(0) ; cout.tie(0) ;
//	rf () ;
	cin >> n >> k ; 
	for ( int i = 1 ; i <= n ; i ++ ) cin >> a [i].l >> a [i].r ; 
	
	mapping () ; 
	
	build_count () ; 
	
	set <pii> S ; 
	S.insert ({0,1}) ; 
	S.insert ({N,N+1}) ; 
	vi res ; 
	
	int can = count_range (1,N) ; 
	for ( int i = 1 ; i <= n ; i ++ ) 
	{
		int l = a[i].l , r = a[i].r ; 
		auto it = S.lower_bound({r,0}) ;
		int rig = it->first ; 
		int lef = (--it)->second ; 
		if ( lef > l ) continue ; 
		
		if ( count_range (lef,l) + count_range (r,rig) + 1 - count_range (lef,rig) + can >= k ) 
		{
			can += count_range (lef,l) + count_range (r,rig) - count_range (lef,rig) + 1 ; 
			S.insert ({l,r}) ; 
			res . pb (i) ; 
			if ( res.size () == k ) break ;  
		} 
	}
	if ( res.size () == k ) 
	{
		for ( auto x : res ) cout << x << "\n" ; 
		re 
	}
	cout << - 1 ; 
}




//-std=c++11

컴파일 시 표준 에러 (stderr) 메시지

event2.cpp: In function 'int main()':
event2.cpp:129:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  129 |    if ( res.size () == k ) break ;
      |         ~~~~~~~~~~~~^~~~
event2.cpp:132:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  132 |  if ( res.size () == k )
      |       ~~~~~~~~~~~~^~~~
event2.cpp: In function 'void rf()':
event2.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 61 / 61