Submission #1099240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099240		cpptowin	Road Construction (JOI21_road_construction)	C++17	100 / 100	7537 ms	135684 KiB

road_construction

#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
void add(int &x, int k)
{
    x += k;
    x %= mod;
    if (x < 0)
        x += mod;
}
void del(int &x, int k)
{
    x -= k;
    x %= mod;
    if (x < 0)
        x += mod;
}
template <class T>
struct Fenwick_Tree
{
    vector<T> bit_add, bit_sub;
    int n;

    Fenwick_Tree(int n = 0) : n(n), bit_add(n + 1), bit_sub(n + 1) {}

    void clear()
    {
        fill(bit_add.begin(), bit_add.end(), T(0));
        fill(bit_sub.begin(), bit_sub.end(), T(0));
    }

    void update(int u, int v, T val)
    {
        for (int i = u; i <= n; i += i & -i)
        {
            bit_add[i] += val;
            bit_sub[i] += 1LL * (u - 1) * val;
        }
        for (int i = v; i <= n; i += i & -i)
        {
            bit_add[i] -= val;
            bit_sub[i] -= 1LL * v * val;
        }
    }

    void update(int u, T val) { update(u, u, val); }

    T get(int u)
    {
        T ans1 = 0, ans2 = 0;
        for (int i = u; i; i -= i & -i)
        {
            ans1 += bit_add[i];
            ans2 += bit_sub[i];
        }
        return u * ans1 - ans2;
    }

    T get(int l, int r) { return get(r) - get(l - 1); }
};
pii a[maxn];
vi up[maxn];
vector<array<int, 3>> range[maxn];
vi nen1, nen2;
int n, k;
bool check(int d)
{
    fo(i, 0, n) range[i].clear();
    Fenwick_Tree<int> t(n + 5);
    fo(i, 1, n)
    {
        int lx = lower_bound(all(nen1), a[i].fi - d) - nen1.begin() + 1;
        int rx = upper_bound(all(nen1), a[i].fi + d) - nen1.begin();
        int ly = lower_bound(all(nen2), a[i].se - d) - nen2.begin() + 1;
        int ry = upper_bound(all(nen2), a[i].se + d) - nen2.begin();
        range[lx - 1].push_back({ly, ry, -1});
        range[rx].push_back({ly, ry, 1});
    }
    int ans = 0;
    fo(i, 1, n)
    {
        for (int it : up[i])
            t.update(it, 1);
        for (auto [l, r, val] : range[i])
            ans += val * t.get(l, r);
    }
    return ans - n >= 2 * k;
}
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    fo(i, 1, n)
    {
        int x, y;
        cin >> x >> y;
        a[i] = {x - y, x + y};
        nen1.pb(a[i].fi);
        nen2.pb(a[i].se);
    }
    sort(all(nen1));
    sort(all(nen2));
    nen1.erase(unique(all(nen1)), nen1.end());
    nen2.erase(unique(all(nen2)), nen2.end());
    fo(i, 1, n)
    {
        int x = lower_bound(all(nen1), a[i].fi) - nen1.begin() + 1;
        int y = lower_bound(all(nen2), a[i].se) - nen2.begin() + 1;
        up[x].pb(y);
    }
    // cout << check(1);en;
    int l = 1, r = 4e9, ans = 4e9;
    while (l <= r)
    {
        int mid = l + r >> 1;
        if (check(mid))
            ans = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    // cout << ans <<"x";en;
    sort(a + 1, a + n + 1);
    vi v;
    set<pii> st;
    fo(i, 1, n)
    {
        pii now = {a[i].se - ans - 1, inf};
        while (1)
        {
            auto it = st.upper_bound(now);
            if (it == st.end() or it->fi > a[i].se + ans)
                break;
            if (it->se < a[i].fi - ans)
            {
                st.erase(it);
                continue;
            }
            v.pb(max(abs(a[i].se - it->fi), abs(a[i].fi - it->se)));
            now = *it;
        }
        st.insert({a[i].se, a[i].fi});
    }
    sort(all(v));
    fo(i, 0, k - 1) cout << v[i] << "\n";
}

Compilation message (stderr)

road_construction.cpp:130:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  130 | main()
      | ^~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:163:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  163 |         int mid = l + r >> 1;
      |                   ~~^~~
road_construction.cpp: In instantiation of 'Fenwick_Tree<T>::Fenwick_Tree(long long int) [with T = long long int]':
road_construction.cpp:110:30:   required from here
road_construction.cpp:63:9: warning: 'Fenwick_Tree<long long int>::n' will be initialized after [-Wreorder]
   63 |     int n;
      |         ^
road_construction.cpp:62:15: warning:   'std::vector<long long int> Fenwick_Tree<long long int>::bit_add' [-Wreorder]
   62 |     vector<T> bit_add, bit_sub;
      |               ^~~~~~~
road_construction.cpp:65:5: warning:   when initialized here [-Wreorder]
   65 |     Fenwick_Tree(int n = 0) : n(n), bit_add(n + 1), bit_sub(n + 1) {}
      |     ^~~~~~~~~~~~
road_construction.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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