Submission #172760

#	Time	Username	Problem	Language	Result	Execution time	Memory
172760		VEGAnn	Money (IZhO17_money)	C++14	45 / 100	1580 ms	68968 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 = (1 << 20);
const int oo = 2e9;
int a[N], n, f[N], kol[N], pref[N], vl, sg[2 * N];
vector<int> vc;
set<int> st;
set<int>::iterator IT;

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){
    l += N; r += N;
    int res = oo;
    while (l <= r){
        res = min(res, sg[l]);
        res = min(res, sg[r]);
        l = (l + 1) >> 1;
        r = (r - 1) >> 1;
    }
    return res;
}

void update(int ps){
    ps += N;
    sg[ps] = f[ps - N];
    ps >>= 1;
    for (; ps > 0; ps >>= 1)
        sg[ps] = min(sg[ps + ps + 1], sg[ps + ps]);
}

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];
        st.insert(a[i]);
        kol[a[i]]++;
    }
    pref[0] = 0;
    for (int i = 1; i < n; i++)
        pref[i] = pref[i - 1] + bool(a[i] < a[i - 1]);

    f[n] = 0;
    for (int it = n - 1; it >= 0; it--){
        kol[a[it]]--;
        if (kol[a[it]] == 0)
            st.erase(a[it]);
        vl = oo;
        if (sz(st)){
            IT = st.upper_bound(a[it]);
            if (IT != st.end())
                vl = *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: 0 / 55