Submission #1192992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192992		warrenn	Money (IZhO17_money)	C++20	0 / 100	4 ms	8004 KiB

money

#include<bits/stdc++.h>
using namespace std;
#define int long long

struct fenwick{
    vector<int>bit;
    fenwick(){
        bit=vector<int>(1000002,0);
    }

    void update(int x,int val){
        for(int q=x;q<=1000000;q+=(q&-q)){
            bit[q]+=val;
        }
    }
    int query(int idx){
    //    cout<<"idx"<<endl;
        int res=0;
        for(int u=idx;u>0;u-=(u&-u)){
            res+=bit[u];
        }
        return res;
    }
};

signed main(){
    int n;
    cin>>n;
    fenwick ff;
    int a[n+2];
    for(int q=1;q<=n;q++){
        cin>>a[q];
    }
    a[n+1]=1e15;

    int ans=0;  
   // cout<<ff.query(1)<<endl;
    for(int q=1;q<=n;q++){
        //cout<<q<<endl;
        ans++;
        int cur=ff.query(1000000)-ff.query(a[q]);
        ff.update(a[q],1);
        q++;
        while(q<=n && a[q]>a[q-1] && ff.query(a[q]-1)-ff.query(a[q-1])==0){
            ff.update(a[q],1);
            q++;
        }
        if(q==n+1)break;
    }
    cout<<ans<<endl;
}

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