Submission #379597

#	Time	Username	Problem	Language	Result	Execution time	Memory
379597		Andrei_Cotor	Money (IZhO17_money)	C++11	0 / 100	1 ms	384 KiB

money

#include<iostream>
#include<set>

using namespace std;

int A[1000005];
set<int> S;       //chiar daca exista A[i]=A[j], nu ma incurca vreau doar sa verific daca A[i-1] e <= si ce urmeaza dupa A[i-1] e >= (practic daca poate fi inserat dupa A[i-1], si implicit sa fie din aceasi grupa)

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;

    for(int i=1; i<=n; i++)
        cin>>A[i];

    int rez=1;
    S.insert(A[1]);
    for(int i=2; i<=n; i++)
    {
        if(A[i]<A[i-1])
        {
            rez++;
        }
        else
        {
            set<int>::iterator it=S.upper_bound(A[i-1]); //elementul care e in mom de fata dupa A[i-1]

            if(it!=S.end() && A[i]>(*it))
                rez++;
        }

        S.insert(A[i]);
    }

    cout<<rez<<"\n";
    return 0;
}

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