HSGO 2020 TRAFFIC

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

constexpr int N = 1e5 + 5;
constexpr ld eps = 1e-12;
int n, b[N], c[N], d[N];
int pos[N], id[N];
ll k;

struct FenwickTree
{
    int n;
    int a[N];

    FenwickTree()
    {
        memset(a, 0, sizeof a);
    }

    void Assgin(int n)
    {
        this->n = n;
        memset(a, 0, sizeof a);
    }

    void Update(int p, int v)
    {
        for (; p <= n; p += p & -p)
            a[p] += v;
    }

    int Get(int p)
    {
        int ans(0);

        for (; p; p -= p & -p)
            ans += a[p];

        return ans;
    }
} f;

struct Traffic
{
    int id;
    ll x, v;
} a[N];

vector<ld> sx;

void Read()
{
    cin >> n >> k;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[a[i].id = i].x >> a[id[i] = i].v;
        a[i].x *= 10000000;
        a[i].v *= 10000000;
    }
}

#define Find(x, v) (lower_bound(x.begin(), x.end(), (v)) - x.begin() + 1)

ll Get(ld t)
{
    sort(id + 1, id + n + 1, [&](const int &x, const int &y)
         { return a[x].x + a[x].v * t < a[y].x + a[y].v * t; });

    int m = 0;
    for (int i = 1, j = 1; i <= n; ++i)
    {
        ++m;
        while (j <= n && a[id[i]].x + a[id[i]].v * t == a[id[j]].x + a[id[j]].v * t)
            ++j;

        while (i < j)
            pos[id[i++]] = m;

        --i;
    }

    f.Assgin(m);

    ll ans(0);

    for (int i = 1, j = 1; i <= n; ++i)
    {
        while (j <= n && a[i].v == a[j].v)
            ++j;

        for (int h = i; h < j; ++h)
            ans += (b[h] = f.Get(pos[h])) - d[h];

        for (int h = i; h < j; ++h)
            f.Update(pos[h], 1);

        i = j - 1;
    }

    return ans;
}

void Search(ld t)
{
    int piv = 0;
    for (int i = n; i; --i)
        if (b[i] != c[i])
        {
            piv = i;
            break;
        }

    pair<ld, int> ans = {0, 0};

    for (int i = 1; a[i].v != a[piv].v; ++i)
        if (a[i].x >= a[piv].x && a[i].x + a[i].v * t <= a[piv].x + a[piv].v * t)
            ans = max(ans, make_pair((ld)1.0 * (a[i].x - a[piv].x) / (a[piv].v - a[i].v), i));

    cout << min(a[ans.second].id, a[piv].id) << " " << max(a[ans.second].id, a[piv].id);
}

void Print(int a[N])
{
    return;
    for (int i = 1; i <= n; ++i)
        cerr << a[i] << " ";
    cerr << "\n";
}

void Solve()
{
    sort(a + 1, a + n + 1, [&](const Traffic &a, const Traffic &b)
         { return a.v < b.v; });
    {
        Get(0);

        for (int i = 1; i <= n; ++i)
            d[i] = b[i];
    }
    {
        ld l = 0, m, h = 2e6;

        while (h - l >= eps)
        {
            m = (l + h) / 2;

            if (Get(m) < k - 1)
                l = m;
            else
                h = m;
        }
        Get(h);

        for (int i = 1; i <= n; ++i)
            c[i] = b[i];
    }
    {
        ld l = 0, m, h = 2e6;

        while (h - l >= eps)
        {
            m = (l + h) / 2;

            if (Get(m) < k)
                l = m;
            else
                h = m;
        }
        Get(h);
        Search(h);
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Read();
    Solve();
}