oj.uz

Submission #641941

# Submission time Handle Problem Language Result Execution time Memory
641941 2022-09-17T23:39:47 Z maomao90 Road Construction (JOI21_road_construction) C++17
100 / 100
 2039 ms 6512 KB 
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 250005;

int n, k;
ii xy[MAXN];
vll ans;

bool isPos(ll v) {
    int lft = 0;
    set<ii> st;
    int rk = k;
    REP (i, 0, n) {
        auto [x, y] = xy[i];
        while (lft < i && (ll) x - xy[lft].FI > v) {
            st.erase({xy[lft].SE, lft});
            lft++;
        }
        auto ptr = st.lower_bound({y, -1});
        auto optr = ptr;
        while (ptr != st.end() && (ll) ptr -> FI - y <= v) {
            if (--rk <= 0) {
                return 1;
            }
            ptr = next(ptr);
        }
        ptr = optr;
        while (ptr != st.begin() && (ll) y - prev(ptr) -> FI <= v) {
            if (--rk <= 0) {
                return 1;
            }
            ptr = prev(ptr);
        }
        st.insert({y, i});
    }
    return 0;
}

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> n >> k;
    REP (i, 0, n) {
        int x, y; cin >> x >> y;
        xy[i] = {x - y, x + y};
    }
    sort(xy, xy + n);
    ll lo = 0, hi = 4e9 + 5, mid;
    while (lo < hi) {
        mid = lo + hi >> 1;
        if (isPos(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    int lft = 0;
    set<ii> st;
    lo--;
    REP (i, 0, n) {
        auto [x, y] = xy[i];
        while (lft < i && (ll) x - xy[lft].FI > lo) {
            auto ptr = st.find({xy[lft].SE, lft});
            assert(ptr != st.end());
            st.erase(ptr);
            lft++;
        }
        auto ptr = st.lower_bound({y, -1});
        auto optr = ptr;
        while (ptr != st.end() && (ll) ptr -> FI - y <= lo) {
            ans.pb(max((ll) x - xy[ptr -> SE].FI, (ll) ptr -> FI - y));
            ptr = next(ptr);
        }
        ptr = optr;
        while (ptr != st.begin() && (ll) y - prev(ptr) -> FI <= lo) {
            ptr = prev(ptr);
            ans.pb(max((ll) x - xy[ptr -> SE].FI, (ll) y - ptr -> FI));
        }
        st.insert({y, i});
    }
    while (SZ(ans) < k) {
        ans.pb(lo + 1);
    }
    sort(ALL(ans));
    for (ll i : ans) {
        cout << i << '\n';
    }
    return 0;
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:84:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |         mid = lo + hi >> 1;
      |               ~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 4952 KB Output is correct
2 Correct 139 ms 4948 KB Output is correct
3 Correct 110 ms 5060 KB Output is correct
4 Correct 110 ms 5064 KB Output is correct
5 Correct 127 ms 3860 KB Output is correct
6 Correct 3 ms 340 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 5608 KB Output is correct
2 Correct 378 ms 5712 KB Output is correct
3 Correct 100 ms 4876 KB Output is correct
4 Correct 298 ms 5356 KB Output is correct
5 Correct 298 ms 5612 KB Output is correct
6 Correct 307 ms 5580 KB Output is correct
7 Correct 267 ms 4872 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 2252 KB Output is correct
2 Correct 288 ms 2256 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 152 ms 2252 KB Output is correct
5 Correct 373 ms 2260 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 2252 KB Output is correct
2 Correct 288 ms 2256 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 152 ms 2252 KB Output is correct
5 Correct 373 ms 2260 KB Output is correct
6 Correct 455 ms 2256 KB Output is correct
7 Correct 393 ms 2252 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 347 ms 2280 KB Output is correct
11 Correct 107 ms 2256 KB Output is correct
12 Correct 399 ms 2284 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 4952 KB Output is correct
2 Correct 139 ms 4948 KB Output is correct
3 Correct 110 ms 5060 KB Output is correct
4 Correct 110 ms 5064 KB Output is correct
5 Correct 127 ms 3860 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 1000 ms 5212 KB Output is correct
8 Correct 1004 ms 5328 KB Output is correct
9 Correct 111 ms 5080 KB Output is correct
10 Correct 592 ms 4504 KB Output is correct
11 Correct 246 ms 4336 KB Output is correct
12 Correct 448 ms 5312 KB Output is correct
13 Correct 411 ms 3704 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 4952 KB Output is correct
2 Correct 139 ms 4948 KB Output is correct
3 Correct 110 ms 5060 KB Output is correct
4 Correct 110 ms 5064 KB Output is correct
5 Correct 127 ms 3860 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 388 ms 5608 KB Output is correct
8 Correct 378 ms 5712 KB Output is correct
9 Correct 100 ms 4876 KB Output is correct
10 Correct 298 ms 5356 KB Output is correct
11 Correct 298 ms 5612 KB Output is correct
12 Correct 307 ms 5580 KB Output is correct
13 Correct 267 ms 4872 KB Output is correct
14 Correct 234 ms 2252 KB Output is correct
15 Correct 288 ms 2256 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 152 ms 2252 KB Output is correct
18 Correct 373 ms 2260 KB Output is correct
19 Correct 455 ms 2256 KB Output is correct
20 Correct 393 ms 2252 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 347 ms 2280 KB Output is correct
24 Correct 107 ms 2256 KB Output is correct
25 Correct 399 ms 2284 KB Output is correct
26 Correct 1000 ms 5212 KB Output is correct
27 Correct 1004 ms 5328 KB Output is correct
28 Correct 111 ms 5080 KB Output is correct
29 Correct 592 ms 4504 KB Output is correct
30 Correct 246 ms 4336 KB Output is correct
31 Correct 448 ms 5312 KB Output is correct
32 Correct 411 ms 3704 KB Output is correct
33 Correct 2039 ms 6380 KB Output is correct
34 Correct 1946 ms 6472 KB Output is correct
35 Correct 1087 ms 5628 KB Output is correct
36 Correct 600 ms 6260 KB Output is correct
37 Correct 637 ms 6512 KB Output is correct
38 Correct 693 ms 4800 KB Output is correct