제출 #247473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
247473		Vladikus004	Kralj (COCI16_kralj)	C++14	0 / 140	2099 ms	67832 KiB

kralj

#include <bits/stdc++.h>
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;

const int N = 500000 + 5;
int n, a[N], p[N], v[N], us[N], cnt, sz[N], was_ed[N];
vector <int> gr[N], add[N];

void add_ed(int x){
    if (was_ed[x]) return;
    gr[(x - 1 + n) % n].push_back(x);
    was_ed[x] = 1;
}

int ans = 0;
multiset <int> ms;
void dfs(int x){
    us[x] = 1;
    if (gr[x].size()) dfs(gr[x][0]);
    ms.insert(p[x]);
    for (auto u: add[x]){
        auto it = ms.lower_bound(u);
        if (it == ms.begin()){
            ms.erase(ms.lower_bound(*ms.rbegin()));
        }else{
            --it;
            ms.erase(it);
            ans++;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> p[i];
    for (int i = 0; i < n; i++) cin >> v[i];
    for (int i = 0; i < n; i++){
        a[i]--;
        int go = 0, ind = a[i];
        do{
            go += sz[ind];
            if (ind != a[i]){
                add_ed(ind);
                sz[a[i]] += sz[ind];
                sz[ind] = 0;
            }
            ind++;
            ind %= n;
        }while (go--);
        add[a[i]].push_back(v[i]);
        sz[a[i]]++;
    }
    for (int i = 0; i < n; i++){
        if (was_ed[i] || us[i]) continue;
        dfs(i);
    }
    cout << ans;
}

• Subtask 1: 0 / 140