oj.uz

Submission #1098644

# Submission time Handle Problem Language Result Execution time Memory
1098644 2024-10-09T16:19:24 Z flyingkite Road Construction (JOI21_road_construction) C++17
100 / 100
 5580 ms 131656 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 230;
ll n, k;
pll a[N];
vector<ll>ans;
struct segment_tree{
    ll n;
    vector<vector<pll>>st;
    void init(ll _n){
        n = _n;
        st.resize(4 * n + 10);
        build(1,1,n);
    }
    vector<pll>merge(const vector<pll>&a, const vector<pll>&b){
        ll i = 0, j = 0;
        vector<pll>res;
        while(i < a.size() && j < b.size()){
            if(a[i].F <= b[j].F) res.pb(a[i++]);
            else res.pb(b[j++]);
        }
        while(i < a.size()) res.pb(a[i++]);
        while(j < b.size()) res.pb(b[j++]);
        return res;
    }
    void build(ll id, ll l, ll r){
        if(l == r){
            st[id].pb({a[l].S, l});
            return;
        }
        ll mid = (l + r) / 2;
        build(2 * id, l, mid);
        build(2 * id + 1, mid + 1, r);
        st[id] = merge(st[2 * id], st[2 * id + 1]);
    }
    ll get(ll id, ll l, ll r, ll left, ll right, ll L, ll R){
        if(l > right || r < left) return 0;
        if(left <= l && r <= right){
            ll i = upper_bound(all(st[id]), make_pair(R, inf)) - st[id].begin() - 1;
            ll j = lower_bound(all(st[id]), make_pair(L, -inf)) - st[id].begin();
            if(j >= (ll)st[id].size()) return 0;
            return i - j + 1;
        }
        ll mid = (l + r) / 2;
        return (get(2 * id, l, mid, left, right, L, R) + get(2 * id + 1, mid + 1, r, left, right, L, R));
    }
    void get_order(ll id, ll l, ll r, ll left, ll right, ll L, ll R, ll idx){
        if(l > right || r < left) return;
        if(left <= l && r <= right){
            ll i = upper_bound(all(st[id]), make_pair(R, inf)) - st[id].begin() - 1;
            ll j = lower_bound(all(st[id]), make_pair(L, -inf)) - st[id].begin();
            if(j >= (ll)st[id].size()) return;
            for(int x = j; x <= i;x++){
                ll cur = st[id][x].S;
                ans.pb(max(abs(a[cur].F - a[idx].F), abs(a[cur].S - a[idx].S)));
            }
            return;
        }
        ll mid = (l + r) / 2;
        get_order(2 * id, l, mid, left, right, L, R, idx);
        get_order(2 * id + 1, mid + 1, r, left, right, L, R, idx);
    }
    ll get(ll l, ll r, ll L, ll R){return get(1,1,n,l,r,L,R);}
} st;
bool check(ll val){
    ll j = 1, cnt = 0;
    for(int i = 1; i <= n;i++){
        while(j < i && a[i].F - a[j].F > val) j++;
        if(j < i) cnt += st.get(j, i - 1, a[i].S - val, a[i].S + val);
    }
    return cnt >= k;
}
void add_order(ll val){
    ll j = 1;
    for(int i = 1; i <= n;i++){
        while(j < i && a[i].F - a[j].F > val) j++;
        if(j < i) {
            st.get_order(1,1,n,j, i - 1, a[i].S - val, a[i].S + val, i); 
        }
    }
}
void to_thic_cau(){
    cin >> n >> k;
    for(int i = 1; i <= n;i++){
        ll x,y; cin >> x >> y;
        a[i].F = x - y, a[i].S = x + y;
    }
    sort(a + 1, a + n + 1);
    st.init(n);
    ll l = 0, r = 5e9, res = -1;
    while(l <= r){
        ll mid = (l + r) / 2;
        if(check(mid)) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    add_order(res);
    sort(all(ans));
    for(int i = 0; i < k;i++) cout << ans[i] << '\n';
}
 
signed main()   
{  
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

Compilation message

road_construction.cpp: In member function 'std::vector<std::pair<long long int, long long int> > segment_tree::merge(const std::vector<std::pair<long long int, long long int> >&, const std::vector<std::pair<long long int, long long int> >&)':
road_construction.cpp:29:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         while(i < a.size() && j < b.size()){
      |               ~~^~~~~~~~~~
road_construction.cpp:29:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         while(i < a.size() && j < b.size()){
      |                               ~~^~~~~~~~~~
road_construction.cpp:33:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         while(i < a.size()) res.pb(a[i++]);
      |               ~~^~~~~~~~~~
road_construction.cpp:34:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         while(j < b.size()) res.pb(b[j++]);
      |               ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5460 KB Output is correct
2 Correct 58 ms 5312 KB Output is correct
3 Correct 50 ms 5320 KB Output is correct
4 Correct 48 ms 5388 KB Output is correct
5 Correct 37 ms 4288 KB Output is correct
6 Correct 6 ms 856 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1840 ms 120888 KB Output is correct
2 Correct 1837 ms 120868 KB Output is correct
3 Correct 42 ms 5352 KB Output is correct
4 Correct 1524 ms 123180 KB Output is correct
5 Correct 1862 ms 124864 KB Output is correct
6 Correct 1941 ms 124964 KB Output is correct
7 Correct 1964 ms 123028 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3286 ms 119492 KB Output is correct
2 Correct 3630 ms 119492 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1712 ms 119564 KB Output is correct
5 Correct 3171 ms 125984 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3286 ms 119492 KB Output is correct
2 Correct 3630 ms 119492 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1712 ms 119564 KB Output is correct
5 Correct 3171 ms 125984 KB Output is correct
6 Correct 3992 ms 119508 KB Output is correct
7 Correct 3505 ms 119380 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 3542 ms 119460 KB Output is correct
11 Correct 1762 ms 119496 KB Output is correct
12 Correct 3217 ms 119520 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5460 KB Output is correct
2 Correct 58 ms 5312 KB Output is correct
3 Correct 50 ms 5320 KB Output is correct
4 Correct 48 ms 5388 KB Output is correct
5 Correct 37 ms 4288 KB Output is correct
6 Correct 6 ms 856 KB Output is correct
7 Correct 2155 ms 55328 KB Output is correct
8 Correct 2009 ms 55328 KB Output is correct
9 Correct 50 ms 5400 KB Output is correct
10 Correct 1335 ms 54560 KB Output is correct
11 Correct 1182 ms 54588 KB Output is correct
12 Correct 1177 ms 56456 KB Output is correct
13 Correct 1517 ms 55656 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5460 KB Output is correct
2 Correct 58 ms 5312 KB Output is correct
3 Correct 50 ms 5320 KB Output is correct
4 Correct 48 ms 5388 KB Output is correct
5 Correct 37 ms 4288 KB Output is correct
6 Correct 6 ms 856 KB Output is correct
7 Correct 1840 ms 120888 KB Output is correct
8 Correct 1837 ms 120868 KB Output is correct
9 Correct 42 ms 5352 KB Output is correct
10 Correct 1524 ms 123180 KB Output is correct
11 Correct 1862 ms 124864 KB Output is correct
12 Correct 1941 ms 124964 KB Output is correct
13 Correct 1964 ms 123028 KB Output is correct
14 Correct 3286 ms 119492 KB Output is correct
15 Correct 3630 ms 119492 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1712 ms 119564 KB Output is correct
18 Correct 3171 ms 125984 KB Output is correct
19 Correct 3992 ms 119508 KB Output is correct
20 Correct 3505 ms 119380 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 3542 ms 119460 KB Output is correct
24 Correct 1762 ms 119496 KB Output is correct
25 Correct 3217 ms 119520 KB Output is correct
26 Correct 2155 ms 55328 KB Output is correct
27 Correct 2009 ms 55328 KB Output is correct
28 Correct 50 ms 5400 KB Output is correct
29 Correct 1335 ms 54560 KB Output is correct
30 Correct 1182 ms 54588 KB Output is correct
31 Correct 1177 ms 56456 KB Output is correct
32 Correct 1517 ms 55656 KB Output is correct
33 Correct 5580 ms 123692 KB Output is correct
34 Correct 5489 ms 123696 KB Output is correct
35 Correct 4038 ms 122920 KB Output is correct
36 Correct 2883 ms 131656 KB Output is correct
37 Correct 3176 ms 131620 KB Output is correct
38 Correct 3805 ms 125740 KB Output is correct