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
#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;
}
# 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