Submission #60486857

---

Source Code Expand

#include <bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
typedef vector<ll> vi;
constexpr ll inf=1ll<<61;
constexpr ll mod=998244353;
typedef modint1000000007 mi;

int a[200005];
mi dp[200005];

int main(){
    int n;ll k;
    cin>>n>>k;
    rep(i,n)cin>>a[i];

    map<int,int>M;
    rep(i,n)M[a[i]]++;
    int cnt=0;
    for(auto &e:M){
        e.second=cnt;
        cnt++;
    }
    rep(i,n)a[i]=M[a[i]];

    ll inv=0;
    fenwick_tree<ll>fw(n);

    int L=0,R=0;

    for(;L<n;L++){
        while(R<n){
            if(inv+fw.sum(a[R]+1,n)<=k){
                inv+=fw.sum(a[R]+1,n);
                fw.add(a[R],1);
                R++;
            }
            else{
                break;
            }
        }
        inv-=fw.sum(0,a[L]);
        fw.add(a[L],-1);
        if(L==0){
            dp[L]+=1;
            dp[R+1]-=1;
            dp[L+1]+=dp[L];
        }
        else{
            dp[L+1]+=2*dp[L];
            dp[R+1]-=dp[L];
        }
    }
    cout<<dp[n].val()<<endl;
}

Submission Info

Judge Result