Submission #85039

#	Time	Username	Problem	Language	Result	Execution time	Memory
85039		igzi	Money (IZhO17_money)	C++17	100 / 100	436 ms	16268 KiB

money

#include <bits/stdc++.h>
#define maxN 1000005

using namespace std;

int a[maxN],ans,tmp,d,n,i,f[maxN];

void update(int p,int v){
while(p<maxN){
    f[p]+=v;
    p+=p & (-p);
}
}

int query(int p){
int ans=0;
while(p>0){
    ans+=f[p];
    p-=p & (-p);
}
return ans;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin>>n;
    for(i=0;i<n;i++) {cin>>a[i]; update(a[i],1);}
    d=n-1;
    ans=1;
    for(i=n-1;i>0;i--){
        update(a[i],-1);
        if(a[i-1]>a[i]){d=i-1; ans++; continue;}
        if(a[i]==a[i-1]) continue;
        tmp=query(a[d]-1)-query(a[i-1]);
        if(tmp==0) continue;
        d=i-1;
        ans++;
    }
    sort(a,a+n);
    //for(i=0;i<n;i++) cout<<a[i]<<" ";
    cout<<ans<<endl;
    return 0;
}

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