Submission #1161156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161156		Doncho_Bonboncho	Kralj (COCI16_kralj)	C++20	84 / 140	2097 ms	42204 KiB

kralj

#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;
		cerr << out( i ) << out( pref[i] ) << out( p[i] ) << endl;
	}

	cerr << out( mn ) << out( start ) << endl;

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

	ll nas = 0;
	std::set< int > elf;
	bool st = true;
	for( int i=start +1 ; i != start + 1 || 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;
}

• Subtask 1: 84 / 140