Submission #1071739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071739		prvocislo	Road Construction (JOI21_road_construction)	C++17	65 / 100	10060 ms	160352 KiB

road_construction

// Lights, camera, b*tch smile, even when you wanna die
// He said he'd love me all his life
// But that life was too short

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
typedef long long ll;
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, sx;
    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, {}), sx.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), sx[x].push_back(i.x);
        }
    }
    int query(ll lx, ll rx, ll ly, ll ry)
    {
        lx = lower_bound(cs.begin(), cs.end(), lx) - cs.begin();
        rx = upper_bound(cs.begin(), cs.end(), rx) - cs.begin();
        int ans = 0;
        for (lx += n, rx += n; 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 (rx & 1) rx--, ans += upper_bound(st[rx].begin(), st[rx].end(), ry) - lower_bound(st[rx].begin(), st[rx].end(), ly);
        }
        return ans;
    }
    void query2(ll lx, ll rx, ll ly, ll ry, vector<ll> &ans, bod b, ll lim)
    {
        lx = lower_bound(cs.begin(), cs.end(), lx) - cs.begin();
        rx = upper_bound(cs.begin(), cs.end(), rx) - cs.begin();
        for (lx += n, rx += n; lx < rx; lx >>= 1, rx >>= 1)
        {
            if (lx & 1)
            {
                int li = lower_bound(st[lx].begin(), st[lx].end(), ly) - st[lx].begin();
                int ri = upper_bound(st[lx].begin(), st[lx].end(), ry) - st[lx].begin();
                for (int i = li; i < ri; i++) ans.push_back(max(abs(st[lx][i] - b.y), abs(sx[lx][i] - b.x)));
                lx++;
            }
            if (rx & 1)
            {
                rx--;
                int li = lower_bound(st[rx].begin(), st[rx].end(), ly) - st[rx].begin();
                int ri = upper_bound(st[rx].begin(), st[rx].end(), ry) - st[rx].begin();
                for (int i = li; i < ri; i++) ans.push_back(max(abs(st[rx][i] - b.y), abs(sx[rx][i] - b.x)));
            }
        }
    }
};
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++)
    {
        //o[i].x = rand() * 10000 + rand(), o[i].y = rand() * 10000 + rand();
        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;
    }
    random_shuffle(v.begin(), v.end());
    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) break;
            cnt += st.query(v[i].x - mi, v[i].x - 1, v[i].y + 1, v[i].y + mi);
            if (cnt >= k) break;
        }
        if (cnt >= k) hi = mi;
        else lo = mi + 1;
    }
    vector<ll> ans;
    for (int i = 0; i < n; i++)
    {
        st.query2(v[i].x - lo + 1, v[i].x, v[i].y - lo + 1, v[i].y, ans, v[i], lo - 1);
        st.query2(v[i].x - lo + 1, v[i].x - 1, v[i].y + 1, v[i].y + lo - 1, ans, v[i], lo - 1);
    }
    sort(ans.begin(), ans.end(), greater<ll>());
    while (ans.size() && ans.back() == 0) ans.pop_back();
    reverse(ans.begin(), ans.end());
    while (ans.size() > k) ans.pop_back();
    while (ans.size() < k) ans.push_back(lo);
    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:21:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bod>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for (int i = 0; i < v.size(); i++) cs.push_back(v[i].x);
      |                         ~~^~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:108:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  108 |     while (ans.size() > k) ans.pop_back();
      |            ~~~~~~~~~~~^~~
road_construction.cpp:109:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |     while (ans.size() < k) ans.push_back(lo);
      |            ~~~~~~~~~~~^~~

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