Submission #172767

#	Time	Username	Problem	Language	Result	Execution time	Memory
172767		VEGAnn	Money (IZhO17_money)	C++14	100 / 100	608 ms	112900 KiB

money

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N = 1000100;
const int PW = 20;
const int oo = 2e9;
int a[N], n, f[N], kol[N], pref[N], vl, sp[N][PW], prec[N], pr[N], nt[N];
vector<int> vc;

bool ok(int l, int r){
    int kl = pref[r] - pref[l];
    if (kl > 0) return 0;
    return (a[r] <= vl);
}

int Min(int l, int r){
    int len = r - l + 1;
    return min(sp[l][prec[len]], sp[r - (1 << prec[len]) + 1][prec[len]]);
}

void update(int ps){
    sp[ps][0] = f[ps];
    for (int po = 1; po < PW; po++){
        if (ps + (1 << po) - 1 >= n) break;
        sp[ps][po] = min(sp[ps][po - 1], sp[ps + (1 << (po - 1))][po - 1]);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("in.txt","r",stdin);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        kol[a[i]]++;
    }

    int pre = 0;
    for (int i = 1; i < N; i++){
        pr[i] = pre;
        if (kol[i] > 0)
            pre = i;
    }
    pre = N - 1;
    for (int i = pre - 1; i > 0; i--){
        nt[i] = pre;
        if (kol[i] > 0)
            pre = i;
    }

    pref[0] = 0;
    for (int i = 1; i < n; i++)
        pref[i] = pref[i - 1] + bool(a[i] < a[i - 1]);

    prec[0] = -1;
    for (int i = 1; i <= n; i++)
        prec[i] = prec[i >> 1] + 1;

    f[n] = 0;
    for (int it = n - 1; it >= 0; it--){
        kol[a[it]]--;
        if (kol[a[it]] == 0){
            pr[nt[a[it]]] = pr[a[it]];
            nt[pr[a[it]]] = nt[a[it]];
        }
        vl = nt[a[it]];

        int l = it, r = n - 1;
        while (l < r){
            int md = (l + r + 1) >> 1;
            if (ok(l, md))
                l = md;
            else r = md - 1;
        }
        f[it] = Min(it + 1, l + 1) + 1;
        update(it);
    }
    cout << f[0];
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55