oj.uz

Submission #1080034

# Submission time Handle Problem Language Result Execution time Memory
1080034 2024-08-29T06:27:36 Z coldbr3w Road Construction (JOI21_road_construction) C++17
0 / 100
 4051 ms 121020 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 = 1, r = 1e12, 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(auto x : ans) cout << x << '\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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5312 KB Output is correct
2 Correct 42 ms 5452 KB Output is correct
3 Correct 35 ms 5324 KB Output is correct
4 Correct 35 ms 5324 KB Output is correct
5 Correct 35 ms 4200 KB Output is correct
6 Incorrect 7 ms 796 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2309 ms 118552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3885 ms 115508 KB Output is correct
2 Correct 4051 ms 119748 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Incorrect 2292 ms 121020 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3885 ms 115508 KB Output is correct
2 Correct 4051 ms 119748 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Incorrect 2292 ms 121020 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5312 KB Output is correct
2 Correct 42 ms 5452 KB Output is correct
3 Correct 35 ms 5324 KB Output is correct
4 Correct 35 ms 5324 KB Output is correct
5 Correct 35 ms 4200 KB Output is correct
6 Incorrect 7 ms 796 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5312 KB Output is correct
2 Correct 42 ms 5452 KB Output is correct
3 Correct 35 ms 5324 KB Output is correct
4 Correct 35 ms 5324 KB Output is correct
5 Correct 35 ms 4200 KB Output is correct
6 Incorrect 7 ms 796 KB Output isn't correct
7 Halted 0 ms 0 KB -