Submission #1071668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071668		prvocislo	Road Construction (JOI21_road_construction)	C++17	5 / 100	7442 ms	2097152 KiB

road_construction

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

struct bod
{
    ll x, y;
};
bool cmpy(bod a, bod b) { return a.y < b.y; }
struct sgt2d
{
    int n;
    vector<vector<ll> > st;
    vector<ll> cs;
    void init(vector<bod> v)
    {
        for (int i = 0; i < v.size(); i++) cs.push_back(v[i].x);
        sort(cs.begin(), cs.end()), cs.erase(unique(cs.begin(), cs.end()), cs.end());
        n = cs.size();
        st.assign(n * 2, {});
        sort(v.begin(), v.end(), cmpy);
        for (bod i : v)
        {
            int x = lower_bound(cs.begin(), cs.end(), i.x) - cs.begin();
            for (x += n; x > 0; x >>= 1) st[x].push_back(i.y);
        }
    }
    int query(int lx, int rx, int ly, int ry)
    {
        lx = lower_bound(cs.begin(), cs.end(), lx) - cs.begin();
        rx = lower_bound(cs.begin(), cs.end(), rx) - cs.begin();
        int ans = 0;
        for (lx += n, rx += n + 1; lx < rx; lx >>= 1, rx >>= 1)
        {
            if (lx & 1) ans += upper_bound(st[lx].begin(), st[lx].end(), ry) - lower_bound(st[lx].begin(), st[lx].end(), ly), lx++;
            if (lx & 1) rx--, ans += upper_bound(st[rx].begin(), st[rx].end(), ry) - lower_bound(st[rx].begin(), st[rx].end(), ly);
        }
        return ans;
    }
};
ll divi(ll a, ll b)
{
    if (a < 0) return -((-a) / b);
    return a / b;
}
sgt2d st;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<bod> o(n), v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> o[i].x >> o[i].y;
        v[i].x = o[i].x + o[i].y;
        v[i].y = o[i].x - o[i].y;
    }
    st.init(v);
    ll lo = 1, hi = 1e10;
    while (lo < hi)
    {
        ll mi = (lo + hi) / 2;
        ll cnt = 0;
        for (int i = 0; i < n; i++) cnt += st.query(v[i].x - mi, v[i].x, v[i].y - mi, v[i].y) - 1;
        if (cnt >= k) hi = mi;
        else lo = mi + 1;
    }
    map<pair<ll, ll>, vector<int> > m;
    for (int i = 0; i < n; i++) m[{divi(v[i].x, lo), divi(v[i].y, lo)}].push_back(i);
    vector<ll> ans;
    for (auto it : m)
    {
        vector<int> t = it.second;
        for (int i = 0; i < t.size(); i++) for (int j = 0; j < i; j++)
            ans.push_back(abs(o[t[i]].x - o[t[j]].x) + abs(o[t[i]].y - o[t[j]].y));
    }
    sort(ans.begin(), ans.end());
    while (ans.size() > k) ans.pop_back();
    while (ans.size() < k) ans.push_back(lo / 2);
    for (int i = 0; i < k; i++) cout << ans[i] << "\n";
    return 0;
}

Compilation message (stderr)

road_construction.cpp: In member function 'void sgt2d::init(std::vector<bod>)':
road_construction.cpp:31:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bod>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for (int i = 0; i < v.size(); i++) cs.push_back(v[i].x);
      |                         ~~^~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for (int i = 0; i < t.size(); i++) for (int j = 0; j < i; j++)
      |                         ~~^~~~~~~~~~
road_construction.cpp:94:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |     while (ans.size() > k) ans.pop_back();
      |            ~~~~~~~~~~~^~~
road_construction.cpp:95:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |     while (ans.size() < k) ans.push_back(lo / 2);
      |            ~~~~~~~~~~~^~~

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