제출 #1161158

#제출 시각아이디문제언어결과실행 시간메모리
1161158Doncho_BonbonchoKralj (COCI16_kralj)C++20
140 / 140
308 ms61160 KiB
#include <algorithm>
#include <bits/stdc++.h>
#include <exception>
#include <variant>
#include <vector>
using namespace std;

#ifndef LOCAL
#define cerr if(false) cerr
#endif

#define out( x ) #x << " = " << x << "  "
#define endl "\n"

template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }

typedef long long ll;
const ll mod = 1e9 +7;
const int MAX_N = 1e6 + 42;

std::vector< int > v[MAX_N];

int main(){
#ifndef LOCAL
	std::ios_base::sync_with_stdio( false ); std::cin.tie( NULL ); std::cout.tie( NULL );
#endif

	int n;
	std::cin >> n;

	std::vector< int > a( n );
	std::vector< int > d( n );
	std::vector< int > e( n );

	std::vector< int > cnt( n );
	for( int i=0 ; i < n ; i++ ){
		std::cin >> a[i];
		cnt[a[i]-1] ++;
		v[a[i]-1].push_back( i );
	}

	std::vector< int > pref( n, 0 );
	std::vector< int > p( n, 0 );
	int mn = mod;
	int start = -1;
	for( int i=0 ; i < n ; i++ ){
		if( i ) pref[i] = pref[i-1];
		pref[i] += cnt[i];
		p[i] = pref[i] - ( i +1 ) ;
		if( chkmin( mn, p[i] ) ) start = i;
	}

	for( auto& j : d ) std::cin >> j;
	for( auto& j : e ) std::cin >> j;

	ll nas = 0;
	std::set< int > elf;
	//std::set< int > dudje;
	bool st = true;
	for( int i= ( start +1 ) % n ; i != ( start + 1 ) % n ||  st ; i = ( i + 1 ) % n ){
		st = false;
		for( auto j : v[i] ) elf.insert( e[j] );

		auto it = elf.lower_bound( d[i] );
		if( it != elf.end() ){
			nas ++;
			elf.erase( it );
		}else elf.erase( elf.begin() );
	}
	std::cout << nas << endl;


	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...