Submission #74691050

---

Source Code Expand

#pragma once

#include <vector>
#include <cmath>
#include <cstdint>
#include <algorithm>
#include <limits>
#include <functional>

template <typename T>
class SegTree
{
public:
    SegTree(std::uint64_t size) :
        m_baseSize{ (std::uint64_t)1 << (std::uint64_t)std::ceil(std::log2(size)) },
        m_tree(m_baseSize << 1, T{})
    {
    }

    SegTree(const std::vector<T>& elems) :
        m_baseSize{ (std::uint64_t)1 << (std::uint64_t)std::ceil(std::log2(elems.size())) },
        m_tree(m_baseSize << 1, T{})
    {
        for (std::uint64_t i = 0; i < elems.size(); i++)
        {
            m_tree[m_baseSize + i] = elems[i];
        }
        for (std::uint64_t i = m_baseSize - 1; i > 0; i--)
        {
            m_tree[i] = T::calc(
                m_tree[i << 1],
                m_tree[(i << 1) + 1]
            );
        }
    }

    T query(std::uint64_t l, std::uint64_t r) const
    {
        return this->queryRecursive(1, 0, m_baseSize - 1, l, r);
    }

    void update(std::uint64_t pos, const T& val)
    {
        this->updateRecursive(1, 0, m_baseSize - 1, pos, val);
    }

    T getElem(std::uint64_t pos) const
    {
        return m_tree[m_baseSize + pos];
    }

    template <typename U>
    friend class SegTree2d;

private:
    T queryRecursive(std::uint64_t startPos, std::uint64_t lRange, std::uint64_t rRange, std::uint64_t l, std::uint64_t r) const
    {
        if (l <= lRange && rRange <= r)
        {
            return m_tree[startPos];
        }

        if (rRange < l || r < lRange)
        {
            return T{};
        }

        std::uint64_t mid = (lRange + rRange) >> 1;

        return T::calc(
            this->queryRecursive(startPos << 1, lRange, mid, l, r),
            this->queryRecursive((startPos << 1) + 1, mid + 1, rRange, l, r)
        );
    }

    void updateRecursive(std::uint64_t startPos, std::uint64_t lRange, std::uint64_t rRange, std::uint64_t pos, const T& val)
    {
        if (lRange == rRange)
        {
            m_tree[startPos] = val;
            return;
        }

        std::uint64_t mid = (lRange + rRange) >> 1;

        if (pos <= mid)
        {
            this->updateRecursive(startPos << 1, lRange, mid, pos, val);
        }
        else
        {
            this->updateRecursive((startPos << 1) + 1, mid + 1, rRange, pos, val);
        }

        m_tree[startPos] = T::calc(
            m_tree[startPos << 1],
            m_tree[(startPos << 1) + 1]
        );
    }

    std::uint64_t m_baseSize;
    std::vector<T> m_tree;
};

struct Sum
{
    std::int64_t val = 0;

    static Sum calc(const Sum& left, const Sum& right)
    {
        return Sum{ left.val + right.val };
    }
};

#pragma GCC optimize("O3")

#include <iostream>
#include <cmath>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <numeric>
#include <bitset>
#include <cstdint>

using namespace std;

using ll = int64_t;

ll calc(const vector<int>& a, int n, ll k)
{
    if (k <= 0) {
        return (ll)n * (n + 1) / 2;
    }

    SegTree<Sum> freqOnPref(n);

    int r = 0;
    ll invs = 0;
    ll res = 0;
    
    for (int l = 0; l < n; ++l)
    {
        while (r < n && invs < k)
        {
            if (a[r] < n - 1)
            {
                invs += freqOnPref.query(a[r] + 1, n - 1).val;
            }
            freqOnPref.update(a[r], Sum{ 1 });
            ++r;
        }

        if (invs >= k)
        {
            res += n - r + 1;
        }

        if (a[l] > 0)
        {
            invs -= freqOnPref.query(0, a[l] - 1).val;
        }
        freqOnPref.update(a[l], Sum{ 0 });
    }

    return res;
}
void solve()
{
    int n;
    ll k;
    cin >> n >> k;

    vector<int> a(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        --a[i];
    }

    cout << calc(a, n, k) - calc(a, n, k + 1) << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;

    while (t--)
    {
        solve();
    }

    return 0;
}

Submission Info

Compile Error

./Main.cpp:1:9: warning: '#pragma once' in main file [-Wpragma-once-outside-header]
    1 | #pragma once
      |         ^~~~

Judge Result