Submission #1295040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295040		AHOKA	Road Construction (JOI21_road_construction)	C++20	27 / 100	2541 ms	29788 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) / 2)
#define lc (2 * id)
#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;

vector<int> v[maxn];

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

int fen[maxn];

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

int gi[maxn];

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

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

    for (int i = 1; i <= n; i++)
        fen[i] = 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) - 1) - get(id(a[i].S - a[i].F - x) - 1);

        add(gi[i], 1);
    }

    return res;
}

int p[2][maxn];

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

    if(k > 100000)
        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++)
        v[gi[i] = id(a[i].S - a[i].F)].push_back(i);

    ll l = 1, 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);

    int j = 1;
    for (int i = 1; i <= n; i++)
    {
        while ((a[i].F + a[i].S) - (a[j].F + a[j].S) > l)
        {
            p[0][gi[j]]++;
            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++)
            for (int ii = p[0][o]; ii < p[1][o];ii++)
                ans.push_back(abs(a[i].F - a[v[o][ii]].F) + abs(a[i].S - a[v[o][ii]].S));

        p[1][gi[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:87:19: warning: division by zero [-Wdiv-by-zero]
   87 |         cout << 1 / 0;
      |                 ~~^~~

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