Submission #248060

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
248060	2020-07-12T07:48:53 Z	Vladikus004	Kralj (COCI16_kralj)	C++14	140 / 140	737 ms	113784 KB

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], cmp[N], pr[N], 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 get_anc(int x){
    if (x == pr[x]) return x;
    return pr[x] = get_anc(pr[x]);
}

void unite(int x, int y){
    x = get_anc(x);
    y = get_anc(y);
    if (x == y) return;
    pr[y] = x;
    ed[x] = ed[y];
}

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

void init(){
    for (int i = 0; i < n; i++)
        ed[i] = -1, pr[i] = i;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n;
    init();
    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]--;
        add[a[i]].push_back(v[i]);
        int go = 0, ind = a[i], e = 0;
        if (!cmp[ind]){
            cmp[ind] = ++cnt;
            ed[cmp[ind]] = ind + 1;
            continue;
        }
        cmp[ind] = get_anc(cmp[ind]);
        int was = ind, was_cmp = cmp[ind];
        ind = ed[cmp[ind]];
        ind %= n;
        while (cmp[ind]){
            add_ed(ind);
            cmp[ind] = get_anc(cmp[ind]);
            unite(cmp[was], cmp[ind]);
            was = ind;
            ind = ed[cmp[ind]];
            ind %= n;
        }
        cmp[ind] = was_cmp;
        add_ed(ind);
        ed[was_cmp]++;
        ed[was_cmp] %= n;
    }
    for (int i = 0; i < n; i++){
        if (was_ed[i] || us[i]) continue;
        dfs(i);
    }
    cout << ans;
}

Compilation message

kralj.cpp: In function 'int main()':
kralj.cpp:70:13: warning: unused variable 'go' [-Wunused-variable]
         int go = 0, ind = a[i], e = 0;
             ^~
kralj.cpp:70:33: warning: unused variable 'e' [-Wunused-variable]
         int go = 0, ind = a[i], e = 0;
                                 ^

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	689 ms	96868 KB	Output is correct
2	Correct	465 ms	94720 KB	Output is correct
3	Correct	621 ms	111972 KB	Output is correct
4	Correct	621 ms	113784 KB	Output is correct
5	Correct	552 ms	88696 KB	Output is correct
6	Correct	568 ms	88000 KB	Output is correct
7	Correct	660 ms	94184 KB	Output is correct
8	Correct	556 ms	87672 KB	Output is correct
9	Correct	737 ms	98168 KB	Output is correct
10	Correct	630 ms	94392 KB	Output is correct