Submission #241507

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
241507	2020-06-24T10:05:15 Z	VEGAnn	Kralj (COCI16_kralj)	C++14	140 / 140	1328 ms	58732 KB

kralj

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define i2 array<int,2>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
const int N = 500100;
const int oo = 2e9;
vector<int> who[N], elms, vls;
vector<i2> vc;
set<int> setik;
set<int>::iterator iter;
int n, a[N], p[N], v[N], st[8 * N], pf[2 * N], cnt[N], loc;
int ans = 0;

void build(int v, int l, int r){
    if (l == r){
        st[v] = pf[l];
        return;
    }

    int md = (l + r) >> 1;

    build(v + v, l, md);
    build(v + v + 1, md + 1, r);

    st[v] = min(st[v + v], st[v + v + 1]);
}

int min(int v, int tl, int tr, int l, int r){
    if (l > r) return oo;

    if (tl == l && tr == r) return st[v];

    int md = (tl + tr) >> 1;

    return min(min(v + v, tl, md, l, min(r, md)),
               min(v + v + 1, md + 1, tr, max(md + 1, l), r));
}

void upd(int &pos){
    pos++;

    if (pos > n)
        pos = 1;
}

int UPD(int pos){
    pos++;

    if (pos > n)
        pos = 1;

    return pos;
}

bool ok(int cnt){
    iter = (--setik.end());

    for (int i = cnt - 1; i >= 0; i--){
        if ((*iter) < vls[i])
            return 0;

        if (i > 0)
            --iter;
    }

    return 1;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        cnt[a[i]]++;

        who[a[i]].PB(i);
    }

    for (int i = 1; i <= n; i++)
        cin >> p[i];

    for (int i = 1; i <= n; i++)
        cin >> v[i];

    pf[0] = 0;

    for (int i = 1; i <= 2 * n; i++){
        pf[i] = pf[i - 1];

        if (i <= n)
            pf[i] += cnt[i];
        else pf[i] += cnt[i - n];
    }

    for (int i = 1; i <= 2 * n; i++)
        pf[i] -= i;

    build(1, 1, n + n);

    loc = -1;

    for (int i = 1; i <= n; i++)
        if (min(1, 1, n + n, i, i + n - 1) == pf[i - 1]){
            loc = i;
            break;
        }

    assert(loc > 0);

    for (int it = 0, pos = loc; it < n; ){
        vc.PB({pos, -1});

        int sum = cnt[pos];

        while (1){
            sum--;

            if (sum == 0) break;

            it++;
            upd(pos);
            sum += cnt[pos];
        }

        vc.back()[1] = pos;

        it++;
        upd(pos);
    }

    for (i2 cr : vc){
        setik.clear();
        elms.clear();

        for (int ps = cr[0]; ; upd(ps)){
            if (cnt[ps] > 0)
                elms.PB(ps);

            if (ps == cr[1]) break;
        }

        elms.PB(UPD(cr[1]));

        for (int it = 0; it < sz(elms) - 1; it++){
            int fi = elms[it], se = elms[it + 1];

            for (int cr : who[fi])
                setik.insert(v[cr]);

            vls.clear();

            for (int j = fi; ; upd(j)){
                vls.PB(p[j]);
                if (UPD(j) == se) break;
            }

            sort(all(vls));

            int l = 0, r = sz(vls);

            while (l < r){
                int md = (l + r + 1) >> 1;

                if (ok(md))
                    l = md;
                else r = md - 1;
            }

            ans += l;

            for (int i = 0; i < l; i++)
                setik.erase(setik.lower_bound(vls[i]));

            for (int i = 0; i < sz(vls) - l; i++)
                setik.erase(setik.begin());
        }
    }

    cout << ans;

    return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1328 ms	51816 KB	Output is correct
2	Correct	504 ms	51048 KB	Output is correct
3	Correct	627 ms	57832 KB	Output is correct
4	Correct	615 ms	58732 KB	Output is correct
5	Correct	622 ms	34356 KB	Output is correct
6	Correct	509 ms	35064 KB	Output is correct
7	Correct	583 ms	38828 KB	Output is correct
8	Correct	529 ms	37828 KB	Output is correct
9	Correct	702 ms	39716 KB	Output is correct
10	Correct	499 ms	36344 KB	Output is correct