Submission #1192706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192706		warrenn	Money (IZhO17_money)	C++20	0 / 100	4 ms	8008 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+1];
    for(int q=1;q<=n;q++){
        cin>>a[q];
    }

    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);
        while(q<n){
            q++;
            int huh=ff.query(1000000)-ff.query(a[q]);
            if(huh!=cur){
                q--;
                break;
            }
            ff.update(a[q],1);
        }
    }
    cout<<ans<<endl;
}

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