提出 #74667062

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
typedef pair<ll,ll> PII;
typedef array<ll,2> a2;
typedef array<ll,3> a3;
ll n,m,k;
int a[N];
ll L[N],R[N];
ll tr[N];

ll lowbit(ll x){
    return x&-x;
}

void add(int x,int c){
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}

ll query(ll x){
    ll sum=0;
    for(int i=x;i>0;i-=lowbit(i)) sum+=tr[i];
    return sum;
}

void __(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    {
        int j=1;
        ll now=0;
        for(int i=1;i<=n;i++){
            ll val=query(n)-query(a[i]);
            add(a[i],1);
            now+=val;
            while(j<=i&&now>m){
                add(a[j],-1);
                now-=query(a[j]);
                j++;
            }
            L[i]=j;
        }
    }
    memset(tr,0,sizeof tr);
    {
        int j=1;
        ll now=0;
        for(int i=1;i<=n;i++){
            ll val=query(n)-query(a[i]);
            add(a[i],1);
            now+=val;
            while(j<=i&&now>=m){
                add(a[j],-1);
                now-=query(a[j]);
                j++;
            }
            R[i]=j;
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++) ans+=R[i]-L[i];
    cout<<ans<<endl;
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _=1;
    // cin>>_;
    while(_--){
        __();
    }
}

提出情報

ジャッジ結果