# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1174690 | nuutsnoynton | Kralj (COCI16_kralj) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5 + 2;
vector < ll > index[N];
int main() {
ll n, m, r,lo, hi,can, tool, mid, x, y, i, j, ans, t, ind_;
cin >> n;
ll ind[n + 2], b[n + 2], a[n + 2], cnt[n + 2], cnt1[n + 2];
for (i = 1; i <= n; i ++) {
cnt[i] = 0;
}
ans = 0;
for (i = 1; i <= n; i ++) {
cin >> ind_;
index[ind_].push_back(i);
cnt[ind_] ++;
}
for (i = 1; i <= n; i ++) cnt1[i]= cnt[i];
for (i = 1; i <= n; i ++) cin >> b[i];
for (i = 1; i <= n; i ++) cin >> a[i];
r = -1;
for (i = 1; i < n; i ++) {
if( cnt1[i] <= 1) {
r = i;
continue;
}
cnt1[i + 1] = cnt1[i + 1] + cnt[i] - 1;
cnt1[i] = 1;
}
if( cnt1[n] <= 1) r = n;
r ++;
if ( r == n + 1) r -= n;
ans = 0;
tool = 0;
while ( tool < n) {
multiset < ll > MS;
while(tool < n) {
for ( ll X : index[r]) {
MS.insert(a[X]);
}
if ( MS.empty()) break;
auto P = MS.upper_bound(b[r]);
if ( P == MS.end()) {
auto S = MS.begin();
MS.erase(S);
}
else {
ans ++;
MS.erase(P);
}
r ++;
if ( r > n) r-= n;
tool ++;
}
tool ++;
r ++;
if ( r > n) r-= n;
}
cout << ans << endl;
}