oj.uz

Submission #682410

# Submission time Handle Problem Language Result Execution time Memory
682410 2023-01-16T08:12:15 Z vjudge1 Road Construction (JOI21_road_construction) C++17
100 / 100
 3129 ms 21824 KB 
#include <bits/stdc++.h>

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

using namespace std;

#define int long long
#define ll long long
#define vi vector<long long>
#define pb push_back
#define sz(s) (int)s.size()
#define all(v) v.begin(), v.end()
#define show(a) cerr << #a <<" -> "<< a <<"\n"
#define pp pair<int,int>
#define FF first
#define SS second
#define endl "\n"
#define ld long double

const int N = 1e6 + 2, N3 = 1e3 + 6, inf = 1e18 + 7, LOG = 20;
map<char, int> md{{'N', 0}, {'E', 1}, {'S', 2}, {'W', 3}};
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
string stepDir = "RDLU";

int n, k, x[N], y[N];
multiset <int> st;
vector <pp> v;

//bool check(int z) {
//    int cnt = 0;
//    for (int i = 1; i < sz(v); i++) {
//        for (int j = 0; j < i; j++) {
//            if (cnt >= k) return 1;
//            if (abs(v[i].FF - v[j].FF) > z) break;
//            if (abs(v[i].FF - v[j].FF) + abs(v[i].SS - v[j].SS) <= z) {
//                cnt++;
////                cout << abs(v[i].FF - v[j].FF) + abs(y[i] - y[j]) << " " << x[j] << " " << y[j] << " " << cnt << "\n";
//            }
//        }
////        cout << cnt << " ";
//    }
//    return cnt >= k;
//}

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

//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];

        v.pb({x[i], y[i]});
    }
    sort(all(v));
//    int l = 0, r = inf, best = -1;
//    while (l <= r) {
//        int mid = (l + r) / 2;
//        if (check(mid)) {
//            best = mid;
//            r = mid - 1;
//        }
//        else l = mid + 1;
//    }

    vi ans;
    int cnt = 0;
    for (int i = 1; i < sz(v); i++) {
        for (int j = max(0ll, i - 1000); j < i; j++) {
            if (sz(st) < k) {
                st.insert(abs(v[i].FF - v[j].FF) + abs(v[i].SS - v[j].SS));
            }
            else {
                if (*st.rbegin() > abs(v[i].FF - v[j].FF) + abs(v[i].SS - v[j].SS)) {
                    st.erase(st.find(*st.rbegin()));
                    st.insert(abs(v[i].FF - v[j].FF) + abs(v[i].SS - v[j].SS));
                }
            }
        }
    }

    for (auto to : st) {
        cout << to << "\n";
    }



	return 0;
}

Compilation message

road_construction.cpp:3: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
road_construction.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main () {
      | ^~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:74:9: warning: unused variable 'cnt' [-Wunused-variable]
   74 |     int cnt = 0;
      |         ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 14688 KB Output is correct
2 Correct 257 ms 14580 KB Output is correct
3 Correct 212 ms 14668 KB Output is correct
4 Correct 143 ms 14660 KB Output is correct
5 Correct 268 ms 13440 KB Output is correct
6 Correct 5 ms 468 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2489 ms 21144 KB Output is correct
2 Correct 2557 ms 21056 KB Output is correct
3 Correct 125 ms 14532 KB Output is correct
4 Correct 2045 ms 20800 KB Output is correct
5 Correct 1911 ms 21060 KB Output is correct
6 Correct 1843 ms 21060 KB Output is correct
7 Correct 1887 ms 20292 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 968 ms 8248 KB Output is correct
2 Correct 989 ms 8260 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1008 ms 8268 KB Output is correct
5 Correct 1026 ms 8280 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 968 ms 8248 KB Output is correct
2 Correct 989 ms 8260 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1008 ms 8268 KB Output is correct
5 Correct 1026 ms 8280 KB Output is correct
6 Correct 1061 ms 8280 KB Output is correct
7 Correct 1054 ms 8248 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1059 ms 8240 KB Output is correct
11 Correct 1018 ms 8180 KB Output is correct
12 Correct 1095 ms 8204 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 14688 KB Output is correct
2 Correct 257 ms 14580 KB Output is correct
3 Correct 212 ms 14668 KB Output is correct
4 Correct 143 ms 14660 KB Output is correct
5 Correct 268 ms 13440 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 2132 ms 17128 KB Output is correct
8 Correct 1938 ms 17132 KB Output is correct
9 Correct 169 ms 14732 KB Output is correct
10 Correct 2131 ms 16448 KB Output is correct
11 Correct 2485 ms 16368 KB Output is correct
12 Correct 915 ms 17128 KB Output is correct
13 Correct 1269 ms 15588 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 14688 KB Output is correct
2 Correct 257 ms 14580 KB Output is correct
3 Correct 212 ms 14668 KB Output is correct
4 Correct 143 ms 14660 KB Output is correct
5 Correct 268 ms 13440 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 2489 ms 21144 KB Output is correct
8 Correct 2557 ms 21056 KB Output is correct
9 Correct 125 ms 14532 KB Output is correct
10 Correct 2045 ms 20800 KB Output is correct
11 Correct 1911 ms 21060 KB Output is correct
12 Correct 1843 ms 21060 KB Output is correct
13 Correct 1887 ms 20292 KB Output is correct
14 Correct 968 ms 8248 KB Output is correct
15 Correct 989 ms 8260 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1008 ms 8268 KB Output is correct
18 Correct 1026 ms 8280 KB Output is correct
19 Correct 1061 ms 8280 KB Output is correct
20 Correct 1054 ms 8248 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1059 ms 8240 KB Output is correct
24 Correct 1018 ms 8180 KB Output is correct
25 Correct 1095 ms 8204 KB Output is correct
26 Correct 2132 ms 17128 KB Output is correct
27 Correct 1938 ms 17132 KB Output is correct
28 Correct 169 ms 14732 KB Output is correct
29 Correct 2131 ms 16448 KB Output is correct
30 Correct 2485 ms 16368 KB Output is correct
31 Correct 915 ms 17128 KB Output is correct
32 Correct 1269 ms 15588 KB Output is correct
33 Correct 2983 ms 21820 KB Output is correct
34 Correct 3129 ms 21824 KB Output is correct
35 Correct 2908 ms 21048 KB Output is correct
36 Correct 1460 ms 21544 KB Output is correct
37 Correct 1407 ms 21820 KB Output is correct
38 Correct 1863 ms 20288 KB Output is correct