Submission #791221

#	Time	Username	Problem	Language	Result	Execution time	Memory
791221		AndiR	Money (IZhO17_money)	C++14	100 / 100	296 ms	14900 KiB

money

#include <iostream>

using namespace std;
const int Nmax=1000000;

int n, aib[Nmax+1], v[Nmax];
void aib_add(int pos){
    for (int i=pos; i<=Nmax; i+=i&-i)
        aib[i]++;
}
int aib_sum(int l, int r){
    int s=0;
    for (int i=r; i>0; i-=i&-i)
        s+=aib[i];
    for (int i=l-1; i>0; i-=i&-i)
        s-=aib[i];
    return s;
}
int main()
{
    cin>>n;
    for (int i=0; i<n; i++)
        cin>>v[i];
    int mn=0, mx=0, sol=1;
    for (int i=1; i<n; i++){
        if (v[i]>=v[mx]){
            mx=i;
            if (v[mx]-v[mn]>=2)
                if (aib_sum(v[mn]+1, v[mx]-1)>0){
                    sol++;
                    for (int j=mn; j<i; j++)
                        aib_add(v[j]);
                    mn=i;
                }
        }
        else{
            sol++;
            for (int j=mn; j<i; j++)
                aib_add(v[j]);
            mx=mn=i;
        }
    }
    cout<<sol;
    return 0;
}

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