oj.uz

Submission #876226

# Submission time Handle Problem Language Result Execution time Memory
876226 2023-11-21T12:55:34 Z Regulus Road Construction (JOI21_road_construction) C++17
100 / 100
 1852 ms 13908 KB 
#include <bits/stdc++.h>            // pA
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cerr << #x << " = " << (x) << ' '
#define endl cerr << '\n'
#define all(v) (v).begin(), (v).end()
#define SZ(v) (ll)(v).size()
#define lowbit(x) (x)&-(x)
#define pb emplace_back
#define F first
#define S second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

const int N = 3e5+5;
const ll INF = 1e18;
ll n, Q;
pll p[N];
multiset<pll> st;
vector<ll> v;

//#define test

inline bool chk(ll w)
{
    ll i, L=1, x, y;

    st.clear(), v.clear();
    for (i=1; i <= n; ++i)
    {
        while (p[i].F-p[L].F > w)
        {
            #ifdef test
            debug(i), debug(L), debug(w), endl;
            #endif
            st.erase(st.find({p[L].S, p[L].F}));
            ++L;
        }

        for (auto it = st.lower_bound({p[i].S, -INF}); it != st.end(); ++it)
        {
            x = it->S, y = it->F;
            if (y-p[i].S > w) break;
            v.pb(max(abs(x-p[i].F), abs(y-p[i].S)));
            if (SZ(v) >= Q) return 1;
        }
        auto it = st.lower_bound({p[i].S, -INF});
        if (it != st.begin())
        {
            --it;
            for ( ; ; --it)
            {
                x = it->S, y = it->F;
                if (p[i].S-y > w) break;
                v.pb(max(abs(x-p[i].F), abs(y-p[i].S)));
                if (SZ(v) >= Q) return 1;
                if (it == st.begin()) break;
            }
        }
        st.insert({p[i].S, p[i].F});

        #ifdef test
        debug(i), endl;
        for (auto x : st) cerr << x.F << ' ' << x.S << '\n';
        #endif
    }
    return 0;
}

int main(void)
{ IO
    ll i, lb, mid, ub, x, y;

    cin >> n >> Q;
    for (i=1; i <= n; ++i) cin >> x >> y, p[i] = {x+y, x-y};

    sort(p+1, p+n+1);
    #ifndef test
    lb = 0, ub = 1e18;
    while (lb < ub)
    {
        mid = (lb+ub)>>1;
        if (chk(mid)) ub = mid;
        else lb = mid + 1;
    }

    chk(lb-1);
    sort(all(v));
    for (i=0; i < min(Q, SZ(v)); ++i) cout << v[i] << '\n';
    for (i=0; i < max(Q-SZ(v), 0LL); ++i) cout << lb << '\n';

    #else
    endl;
    for (i=1; i <= n; ++i) debug(p[i].F), debug(p[i].S), endl;

    endl;
    chk(2);
    endl;
    for (ll x : v) debug(x), endl;
    #endif


    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 5128 KB Output is correct
2 Correct 156 ms 5076 KB Output is correct
3 Correct 136 ms 5136 KB Output is correct
4 Correct 127 ms 5068 KB Output is correct
5 Correct 174 ms 4044 KB Output is correct
6 Correct 3 ms 348 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 9700 KB Output is correct
2 Correct 321 ms 10940 KB Output is correct
3 Correct 124 ms 4892 KB Output is correct
4 Correct 293 ms 10620 KB Output is correct
5 Correct 277 ms 10784 KB Output is correct
6 Correct 285 ms 10880 KB Output is correct
7 Correct 247 ms 10444 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 9704 KB Output is correct
2 Correct 255 ms 9696 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 108 ms 7876 KB Output is correct
5 Correct 383 ms 9836 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 9704 KB Output is correct
2 Correct 255 ms 9696 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 108 ms 7876 KB Output is correct
5 Correct 383 ms 9836 KB Output is correct
6 Correct 357 ms 9808 KB Output is correct
7 Correct 329 ms 9556 KB Output is correct
8 Correct 0 ms 356 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 270 ms 9796 KB Output is correct
11 Correct 117 ms 7516 KB Output is correct
12 Correct 373 ms 10080 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 5128 KB Output is correct
2 Correct 156 ms 5076 KB Output is correct
3 Correct 136 ms 5136 KB Output is correct
4 Correct 127 ms 5068 KB Output is correct
5 Correct 174 ms 4044 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 931 ms 8596 KB Output is correct
8 Correct 1008 ms 8596 KB Output is correct
9 Correct 133 ms 5136 KB Output is correct
10 Correct 460 ms 8084 KB Output is correct
11 Correct 297 ms 7904 KB Output is correct
12 Correct 369 ms 8812 KB Output is correct
13 Correct 447 ms 7164 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 5128 KB Output is correct
2 Correct 156 ms 5076 KB Output is correct
3 Correct 136 ms 5136 KB Output is correct
4 Correct 127 ms 5068 KB Output is correct
5 Correct 174 ms 4044 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 414 ms 9700 KB Output is correct
8 Correct 321 ms 10940 KB Output is correct
9 Correct 124 ms 4892 KB Output is correct
10 Correct 293 ms 10620 KB Output is correct
11 Correct 277 ms 10784 KB Output is correct
12 Correct 285 ms 10880 KB Output is correct
13 Correct 247 ms 10444 KB Output is correct
14 Correct 183 ms 9704 KB Output is correct
15 Correct 255 ms 9696 KB Output is correct
16 Correct 1 ms 352 KB Output is correct
17 Correct 108 ms 7876 KB Output is correct
18 Correct 383 ms 9836 KB Output is correct
19 Correct 357 ms 9808 KB Output is correct
20 Correct 329 ms 9556 KB Output is correct
21 Correct 0 ms 356 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 270 ms 9796 KB Output is correct
24 Correct 117 ms 7516 KB Output is correct
25 Correct 373 ms 10080 KB Output is correct
26 Correct 931 ms 8596 KB Output is correct
27 Correct 1008 ms 8596 KB Output is correct
28 Correct 133 ms 5136 KB Output is correct
29 Correct 460 ms 8084 KB Output is correct
30 Correct 297 ms 7904 KB Output is correct
31 Correct 369 ms 8812 KB Output is correct
32 Correct 447 ms 7164 KB Output is correct
33 Correct 1802 ms 13704 KB Output is correct
34 Correct 1852 ms 13704 KB Output is correct
35 Correct 1085 ms 12932 KB Output is correct
36 Correct 579 ms 13884 KB Output is correct
37 Correct 545 ms 13908 KB Output is correct
38 Correct 875 ms 12420 KB Output is correct