제출 #1193001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193001		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+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 tmp=q;
        q++;
        while(q<=n && a[q]>=a[q-1] && ff.query(a[q]-1)-ff.query(a[tmp])==0){
            q++;
        }
        for(;tmp<q;tmp++){
            ff.update(a[tmp],1);
        }
        if(q==n+1)break;
        q--;
    }
    cout<<ans<<endl;
}

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