Submission #1080059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080059		coldbr3w	Road Construction (JOI21_road_construction)	C++17	100 / 100	5610 ms	126908 KiB

road_construction

#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 (stderr)

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 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35