제출 #379597

#제출 시각아이디문제언어결과실행 시간메모리
379597Andrei_CotorMoney (IZhO17_money)C++11
0 / 100
1 ms384 KiB
#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;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...