oj.uz

Submission #893446

# Submission time Handle Problem Language Result Execution time Memory
893446 2023-12-27T05:00:51 Z vjudge1 Road Construction (JOI21_road_construction) C++17
100 / 100
 7140 ms 705476 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
using namespace __gnu_pbds;

const int mod = 998244353;
const double PI = acos(-1.0);
const double epsilon = 1e-6;
const int N = 2e5 + 5;

vector<pair<int, int>> a;
multiset<int> ans;
map<pair<pair<int,int>,pair<int,int> >,bool> vis;
int mindist = 1e18;
int n, k;

int dist(pair<int, int> f, pair<int, int> s){
    return abs(f.ff - s.ff) + abs(f.ss - s.ss);
}

void update(pair<int, int> f, pair<int, int> s){
	if(vis[{f,s}] || vis[{s,f}]) return;
    ans.insert(dist(f, s));
    vis[{f,s}] = 1;
    if ((int)ans.size() == k) mindist = *prev(ans.end());
    else if ((int)ans.size() > k) {
        ans.erase(prev(ans.end()));
        mindist = *prev(ans.end());
    }
}

bool cmp(pair<int, int> f, pair<int, int> s){
    return f.ss < s.ss;
}

void rec(int l, int r){
    if (r - l <= 3) {
        for (int i = l; i < r; i++) {
            for (int j = i + 1; j <= r; j++) {
                update(a[i], a[j]);
            }
        }
        sort(a.begin() + l, a.begin() + r + 1, cmp);
        return;
    }

    int m = (l + r) >> 1;
    int midx = a[m].ff;
    rec(l, m), rec(m + 1, r);
    vector<pair<int, int>> t(r - l + 1);
    merge(a.begin() + l, a.begin() + m + 1, a.begin() + m + 1, a.begin() + r + 1, t.begin(), cmp);
    copy(t.begin(), t.begin() + r - l + 1, a.begin() + l);

    int sz = 0;
    for (int i = l; i <= r; i++) {
        if (abs(a[i].ff - midx) < mindist) {
            for (int j = sz - 1; j >= 0 && a[i].ss - t[j].ss < mindist; j--) {
                update(a[i], t[j]);
            }
            t[sz++] = a[i];
        }
    }
}

void solve(){
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a.pb({x, y});
    }
    sort(all(a));
    rec(0, n - 1);
    for (int i : ans) cout << i << '\n';
}

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

Compilation message

road_construction.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main(){
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 944 ms 88728 KB Output is correct
2 Correct 958 ms 88660 KB Output is correct
3 Correct 501 ms 53836 KB Output is correct
4 Correct 457 ms 53936 KB Output is correct
5 Correct 751 ms 74244 KB Output is correct
6 Correct 11 ms 2648 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3323 ms 389920 KB Output is correct
2 Correct 3368 ms 390232 KB Output is correct
3 Correct 362 ms 53572 KB Output is correct
4 Correct 3023 ms 419820 KB Output is correct
5 Correct 2400 ms 378264 KB Output is correct
6 Correct 2311 ms 378348 KB Output is correct
7 Correct 2400 ms 381792 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 65952 KB Output is correct
2 Correct 231 ms 71108 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 197 ms 68816 KB Output is correct
5 Correct 237 ms 71244 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 65952 KB Output is correct
2 Correct 231 ms 71108 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 197 ms 68816 KB Output is correct
5 Correct 237 ms 71244 KB Output is correct
6 Correct 234 ms 71020 KB Output is correct
7 Correct 241 ms 72172 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 239 ms 71148 KB Output is correct
11 Correct 203 ms 68796 KB Output is correct
12 Correct 238 ms 71400 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 944 ms 88728 KB Output is correct
2 Correct 958 ms 88660 KB Output is correct
3 Correct 501 ms 53836 KB Output is correct
4 Correct 457 ms 53936 KB Output is correct
5 Correct 751 ms 74244 KB Output is correct
6 Correct 11 ms 2648 KB Output is correct
7 Correct 5695 ms 563684 KB Output is correct
8 Correct 5576 ms 568376 KB Output is correct
9 Correct 439 ms 53840 KB Output is correct
10 Correct 5537 ms 496640 KB Output is correct
11 Correct 7140 ms 663684 KB Output is correct
12 Correct 3373 ms 490760 KB Output is correct
13 Correct 3614 ms 447892 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 944 ms 88728 KB Output is correct
2 Correct 958 ms 88660 KB Output is correct
3 Correct 501 ms 53836 KB Output is correct
4 Correct 457 ms 53936 KB Output is correct
5 Correct 751 ms 74244 KB Output is correct
6 Correct 11 ms 2648 KB Output is correct
7 Correct 3323 ms 389920 KB Output is correct
8 Correct 3368 ms 390232 KB Output is correct
9 Correct 362 ms 53572 KB Output is correct
10 Correct 3023 ms 419820 KB Output is correct
11 Correct 2400 ms 378264 KB Output is correct
12 Correct 2311 ms 378348 KB Output is correct
13 Correct 2400 ms 381792 KB Output is correct
14 Correct 240 ms 65952 KB Output is correct
15 Correct 231 ms 71108 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 197 ms 68816 KB Output is correct
18 Correct 237 ms 71244 KB Output is correct
19 Correct 234 ms 71020 KB Output is correct
20 Correct 241 ms 72172 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 239 ms 71148 KB Output is correct
24 Correct 203 ms 68796 KB Output is correct
25 Correct 238 ms 71400 KB Output is correct
26 Correct 5695 ms 563684 KB Output is correct
27 Correct 5576 ms 568376 KB Output is correct
28 Correct 439 ms 53840 KB Output is correct
29 Correct 5537 ms 496640 KB Output is correct
30 Correct 7140 ms 663684 KB Output is correct
31 Correct 3373 ms 490760 KB Output is correct
32 Correct 3614 ms 447892 KB Output is correct
33 Correct 6818 ms 704956 KB Output is correct
34 Correct 6737 ms 705476 KB Output is correct
35 Correct 7118 ms 699112 KB Output is correct
36 Correct 3834 ms 594340 KB Output is correct
37 Correct 3821 ms 594476 KB Output is correct
38 Correct 4266 ms 547244 KB Output is correct