Submission #241635

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
241635	2020-06-24T21:35:33 Z	AQT	Kralj (COCI16_kralj)	C++14	140 / 140	824 ms	44648 KB

kralj

// Problem : COCI '16 Contest 1 #5 Kralj
// Contest : DMOJ
// URL : https://dmoj.ca/problem/coci16c1p5
// Memory Limit : 128 MB
// Time Limit : 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>

using namespace std;

int N;
int arr[500005], apow[500005], bpow[500005];
vector<int> v[500005];

int solve(int s){
	set<int> st;
	int ret = 0;
	for(int i = s, c = 0; c<N; c++, i = (i+1)%N){
		for(int n : v[i]){
			st.insert(n);
		}
		if(st.empty()){
			return 0;
		}
		if(st.lower_bound(apow[i]) != st.end()){
			ret++;
			st.erase(st.lower_bound(apow[i]));
		}
		else{
			st.erase(st.begin());
		}
	}
	//cout << s << "\n";
	return ret;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 0; i<N; i++){
		cin >> arr[i];
		arr[i]--;
	}
	for(int i = 0; i<N; i++){
		cin >> apow[i];
		//v[arr[i]].push_back(apow[i]);
	}
	for(int i = 0; i<N; i++){
		cin >> bpow[i];
		v[arr[i]].push_back(bpow[i]);
	}
	int delta = 0, pre = 0;
	deque<pair<int, int>> mn;
	for(int i = 0 ;i<N; i++){
		pre += v[i].size();
		pre--;
		while(mn.size() && mn.back().second > pre){
			mn.pop_back();
		}
		mn.push_back(make_pair(i, pre));
	}
	int ans = -1;
	for(int i = 0; i<N; i++){
		//cout << mn.front().first << " " << mn.front().second-delta << " " << delta << endl;
		if(mn.front().second - delta >= 0){
			//cout << mn.back().second-delta << " " << i << "\n";
			ans = solve(i);
			break;
		}
		/*
		pre += v[i].size();
		pre--;
		*/
		delta += v[i].size();
		delta--;
		//cout << pre << " " << delta << endl;
		if(mn.front().first == i){
			mn.pop_front();
		}
		while(mn.size() && mn.back().second > pre + delta){
			mn.pop_back();
		}
		mn.push_back(make_pair(i, pre+delta));
	}
	assert(ans != -1);
	cout << ans << "\n";
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	824 ms	38756 KB	Output is correct
2	Correct	490 ms	38348 KB	Output is correct
3	Correct	587 ms	43788 KB	Output is correct
4	Correct	588 ms	44648 KB	Output is correct
5	Correct	422 ms	21880 KB	Output is correct
6	Correct	346 ms	22412 KB	Output is correct
7	Correct	494 ms	25336 KB	Output is correct
8	Correct	395 ms	24824 KB	Output is correct
9	Correct	525 ms	25720 KB	Output is correct
10	Correct	417 ms	23032 KB	Output is correct