Submission #74662921

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define se second
#define fi first
#define pb push_back
#define pf push_front
#define ld long double
#define INF 1e18
#define lcm(x, y) x / __gcd(x, y) * y
#define Pair pair<ll, ll>
#define pii pair<int, int>
#define Pq priority_queue<ll>
#define Pqr priority_queue<ll, vector<ll>, greater<ll >>
#define clockst clock_t tStart = clock()
#define clockfin printf("Time taken: %.2fs\n",(double)(clock() - tStart)/CLOCKS_PER_SEC)
#define all(x) x.begin(), x.end()
#define sz(x)((ll)(x).size())
#define eb emplace_back
#define mp make_pair
#define mems(a, x) memset((a),(x), sizeof(a))
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,bmi,bmi2,fma")
typedef unsigned long long ull;
void init() { freopen("cf.INP", "r", stdin); freopen("cf.OUT", "w", stdout); }
ll xc[5] = { -1, 1, 0, 0 }, yc[5] = { 0, 0, 1, -1 };
ll xc8[8] = { -1, 1, 0, 0, -1, 1, -1, 1 };
ll yc8[8] = { 0, 0, 1, -1, -1, 1, 1, -1 };
const long double pi = acosl(-1.0L);
template<class T1, class T2> bool cmax(T1 &x, const T2 &y) { if(x < y) { x = y; return 1; } return 0; }

inline ll read()
{
    ll x = 0;
    char ch = getchar();;
    bool str = 1;
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') str = 0; ch = getchar();;
    }
    while(ch >= '0' && ch <= '9')
    {
        x =((x << 3) +(x << 1)) + ch - '0';
        ch = getchar();;
    }
    return str ? x : x;
}

struct fenwick {
    ll n;
    vector<ll> bit;
    fenwick(ll x) : n(x), bit(x + 2, 0) {}
    void add(ll i, ll delta)
    {
        for (; i <= n; i += i & -i) bit[i] += delta;
    }
    ll sum(ll i)
    {
        ll s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }
    ll query(ll i)
    {
        return sum(i);
    }
};

void solve()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> p(n + 1);
    for (ll i = 1; i <= n; i++) cin >> p[i];
    fenwick blow(n), bhigh(n);
    ll rl = 0, rh = 0, invl = 0, invh = 0, ans = 0;
    for (ll l = 1; l <= n; l++)
    {
        while (rl < n && invl < k)
        {
            rl++;
            ll val = p[rl];
            ll total = rl - l;
            ll it = blow.sum(val - 1);
            invl += total - it;
            blow.add(val, 1);
        }
        while (rh < n && invh <= k)
        {
            rh++;
            ll val = p[rh];
            ll total = rh - l;
            ll it = bhigh.sum(val - 1);
            invh += total - it;
            bhigh.add(val, 1);
        }
        if (rh == n && invh <= k) rh = n + 1;
        if (invl == k)
        {
            ll left = max(l, rl);
            ans += rh - left;
        }
        if (l <= rl)
        {
            ll val = p[l];
            ll it = blow.sum(val - 1);
            invl -= it;
            blow.add(val, -1);
        }
        if (l <= rh)
        {
            ll val = p[l];
            ll it = bhigh.sum(val - 1);
            invh -= it;
            bhigh.add(val, -1);
        }
    }
    cout << ans << '\n';
}

bool multest = 0;

int main()
{
    fast;
    ll t = 1;
    if(multest) cin >> t;
    while(t--) solve();
    return 0;
}

Submission Info

Judge Result