Submission #686620

#	Time	Username	Problem	Language	Result	Execution time	Memory
686620		toma_ariciu	Money (IZhO17_money)	C++17	9 / 100	1 ms	308 KiB

money

/// banii banii banii
/// 2 locuri in masina ca milionarii
#include <iostream>
#include <set>

using namespace std;

int n, v[1000005], ans = 1;
set <int> values;

int solve(int poz)
{
    auto it = values.upper_bound(v[poz]);
    int aux, maxval = (*it);
    bool ok = 1;
    for(aux = poz + 1; aux <= n && ok; aux++)
        if(v[aux] < v[aux - 1] || v[aux] > maxval)
            ok = 0;
    if(!ok)
        aux--;
    for(int i = poz; i < aux; i++)
        values.insert(v[i]);
    return aux;
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> v[i];
    int poz = n + 1;
    for(int i = 2; i <= n && (poz == n + 1); i++)
        if(v[i] < v[i - 1])
            poz = i;
    for(int i = 1; i < poz; i++)
        values.insert(v[i]);
    while(poz <= n)
    {
        poz = solve(poz);
        ans++;
    }
    cout << ans;
    return 0;
}

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