Submission #241498

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
241498	2020-06-24T09:56:27 Z	VEGAnn	Kralj (COCI16_kralj)	C++14	0 / 140	1122 ms	121920 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);
    }

    cout << sz(vc) << '\n';

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

        for (int ps = cr[0]; ; upd(ps)){
            if (ps == cr[1]) break;

            if (cnt[ps] > 0)
                elms.PB(ps);
        }

        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; ; 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]));
        }
    }

    cout << ans;

    return 0;
}

Subtask #1

0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1122 ms	56252 KB	Output isn't correct
2	Incorrect	540 ms	55616 KB	Output isn't correct
3	Incorrect	650 ms	62224 KB	Output isn't correct
4	Incorrect	736 ms	63084 KB	Output isn't correct
5	Runtime error	435 ms	102856 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	588 ms	121920 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	638 ms	111812 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Runtime error	480 ms	109372 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	581 ms	112596 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	587 ms	106432 KB	Execution killed with signal 11 (could be triggered by violating memory limits)