Submission #686625

#	Time	Username	Problem	Language	Result	Execution time	Memory
686625		toma_ariciu	Money (IZhO17_money)	C++17	100 / 100	1188 ms	58080 KiB

money

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

using namespace std;

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

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

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: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55