oj.uz

Submission #1080052

# Submission time Handle Problem Language Result Execution time Memory
1080052 2024-08-29T06:37:10 Z coldbr3w Road Construction (JOI21_road_construction) C++17
32 / 100
 5605 ms 58168 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()
#define int long long
const ll N = 2e5 + 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 = lower_bound(all(st[id]), make_pair(R + 1, -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 = lower_bound(all(st[id]), make_pair(R + 1, -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 = 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(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 41 ms 5324 KB Output is correct
2 Correct 43 ms 5316 KB Output is correct
3 Correct 34 ms 5400 KB Output is correct
4 Correct 38 ms 5324 KB Output is correct
5 Correct 33 ms 4284 KB Output is correct
6 Correct 6 ms 860 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 5605 ms 9568 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 5603 ms 11092 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 5603 ms 11092 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5324 KB Output is correct
2 Correct 43 ms 5316 KB Output is correct
3 Correct 34 ms 5400 KB Output is correct
4 Correct 38 ms 5324 KB Output is correct
5 Correct 33 ms 4284 KB Output is correct
6 Correct 6 ms 860 KB Output is correct
7 Correct 2161 ms 55968 KB Output is correct
8 Correct 2153 ms 55972 KB Output is correct
9 Correct 33 ms 5324 KB Output is correct
10 Correct 1421 ms 55268 KB Output is correct
11 Correct 1234 ms 55132 KB Output is correct
12 Correct 1164 ms 58168 KB Output is correct
13 Correct 1378 ms 57068 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5324 KB Output is correct
2 Correct 43 ms 5316 KB Output is correct
3 Correct 34 ms 5400 KB Output is correct
4 Correct 38 ms 5324 KB Output is correct
5 Correct 33 ms 4284 KB Output is correct
6 Correct 6 ms 860 KB Output is correct
7 Runtime error 5605 ms 9568 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -