Submission #1295092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295092		AHOKA	Road Construction (JOI21_road_construction)	C++20	32 / 100	10096 ms	185536 KiB

road_construction

#include <bits/stdc++.h>

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

using namespace std;
 
#define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define ll long long
#define pii pair<ll, ll>
#define ppp pair<ll, pii>
#define dout cout << fixed << setprecision(15)
#define mid ((l + r) >> 1)
#define lc (id << 1)
#define rc (lc + 1)

mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());

const ll maxn = 25e4 + 10, maxm = 3e3 + 10, oo = 1e18, lg = 31, sq = 1400, mod = 2e9;

int n;
ll k;

vector<ll> cmp;

queue<int> q[maxn];

pii a[maxn];
ppp b[maxn];

int fen[maxn];

inline int id(ll x){
    return lower_bound(all(cmp), x) - cmp.begin();
}

int gi[maxn];

inline void add(int i, int val){
    for (; i <= n; i += i & -i)
        fen[i] += val;
}
 
inline int get(int l, int r){
    int res = 0;
    
    for (; r > 0; r -= r & -r)
        res += fen[r];
    for (; l > 0; l -= l & -l)
        res -= fen[l];

    return res;
}

ll check(ll x){
    int j = 1;
    ll res = 0;

    fill(fen + 1, fen + n + 1, 0);

    for (int i = 1; i <= n; i++)
    {
        while ((a[i].F + a[i].S) - (a[j].F + a[j].S) > x)
        {
            add(gi[j], -1);
            j++;
        }

        res += get(id(a[i].S - a[i].F - x) - 1, id(a[i].S - a[i].F + x + 1) - 1);

        add(gi[i], 1);
    }

    return res;
}

void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n;i++)
        cin >> a[i].F >> a[i].S;

    /*if(k < 20000)
        cout << 1 / 0;*/

    /*n = 250000;
    k = n;
    for (int i = 1; i <= n;i++)
        a[i].F = rng() % mod;

    for (int i = 1; i <= n;i++)
        a[i].S = rng() % mod;*/

    for (int i = 1; i <= n;i++)
        b[i] = {a[i].F + a[i].S, a[i]};

    sort(b + 1, b + n + 1);

    for (int i = 1; i <= n;i++)
        a[i] = b[i].S;

    for (int i = 1; i <= n;i++)
        cmp.push_back(a[i].S - a[i].F);

    cmp.push_back(-oo);

    sort(all(cmp));

    cmp.resize(unique(all(cmp)) - cmp.begin());

    for (int i = 1; i <= n;i++)
        gi[i] = id(a[i].S - a[i].F);

    ll l = 0, r = 2 * mod;
    while(r - l > 1)
        if(check(mid) >= k)
            r = mid;
        else
            l = mid;

    vector<ll> ans;
    for (ll i = 1; i <= k - check(l);i++)
        ans.push_back(r);

    if(check(l) >= k)
        cout << 1 / 0;

    int j = 1;
    for (int i = 1; i <= n; i++)
    {
        while ((a[i].F + a[i].S) - (a[j].F + a[j].S) > l)
        {
            q[gi[j]].pop();
            j++;
        }

        int fm = id(a[i].S - a[i].F - l);
        int to = id(a[i].S - a[i].F + l + 1) - 1;
        for (int o = fm; o <= to; o++){
            int sz = q[o].size();
            for (int ii = 0; ii < sz; ii++)
            {
                ans.push_back(abs(a[i].F - a[q[o].front()].F) + abs(a[i].S - a[q[o].front()].S));
                q[o].push(q[o].front());
                q[o].pop();
            }
        }

        q[gi[i]].push(i);
    }

    sort(all(ans));
    
    for(auto i : ans)
        cout << i << "\n";
}

signed main()
{
    threesum;
    int t = 1;
    //cin >> t;
    while(t--)
        solve();
}

Compilation message (stderr)

road_construction.cpp: In function 'void solve()':
road_construction.cpp:130:19: warning: division by zero [-Wdiv-by-zero]
  130 |         cout << 1 / 0;
      |                 ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35