Submission #443158

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
443158	2021-07-09T23:01:32 Z	penguinhacker	Kralj (COCI16_kralj)	C++14	140 / 140	640 ms	64868 KB

kralj

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=5e5;
int n, a[2*mxN], b[2*mxN], p[2*mxN], cnt[2*mxN], pre[2*mxN], dp[2*mxN], ans;
vector<int> oc[mxN];
set<int> s;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=0; i<n; ++i) {
		cin >> p[i], --p[i];
		++cnt[p[i]], ++cnt[p[i]+n];
		oc[p[i]].push_back(i);
	}
	for (int i=0; i<n; ++i) {
		cin >> a[i];
		a[i+n]=a[i];
	}
	for (int i=0; i<n; ++i) {
		cin >> b[i];
		b[i+n]=b[i];
	}
	for (int i=0; i<2*n; ++i) {
		pre[i]=(i?pre[i-1]:0)+cnt[i];
		dp[i]=pre[i]-i-1;
	}
	deque<int> dq;
	for (int i=0; i<n; ++i) {
		while(dq.size()&&dp[i]<=dp[dq.back()])
			dq.pop_back();
		dq.push_back(i);
	}
	assert(dp[dq[0]]<=0);
	int start=dp[dq[0]]==0?0:-1;
	for (int i=1; i<n&&start==-1; ++i) {
		if (dq[0]<i)
			dq.pop_front();
		while(dq.size()&&dp[i+n-1]<=dp[dq.back()])
			dq.pop_back();
		dq.push_back(i+n-1);
		int cur=dp[dq[0]]-pre[i-1]+i;
		assert(cur<=0);
		if (cur==0)
			start=i;
	}
	assert(start^-1);
	for (int i=0; i<n; ++i) {
		int cur=(start+i)%n;
		for (int j : oc[cur])
			s.insert(b[j]);
		assert(s.size());
		if (a[cur]>*s.rbegin()) {
			s.erase(s.begin());
		} else {
			s.erase(s.lower_bound(a[cur]));
			++ans;
		}
	}
	cout << ans;
	return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	640 ms	55236 KB	Output is correct
2	Correct	405 ms	53688 KB	Output is correct
3	Correct	494 ms	63960 KB	Output is correct
4	Correct	507 ms	64868 KB	Output is correct
5	Correct	384 ms	46532 KB	Output is correct
6	Correct	350 ms	46276 KB	Output is correct
7	Correct	448 ms	50884 KB	Output is correct
8	Correct	375 ms	47660 KB	Output is correct
9	Correct	471 ms	53016 KB	Output is correct
10	Correct	409 ms	49596 KB	Output is correct