oj.uz

Submission #682292

# Submission time Handle Problem Language Result Execution time Memory
682292 2023-01-16T05:48:41 Z armashka Road Construction (JOI21_road_construction) C++17
100 / 100
 6923 ms 26940 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
using namespace __gnu_pbds;
 
template<class T> using ordered_multiset =tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update> ;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file(s) freopen(s".in", "r", stdin);freopen(s".out", "w", stdout);
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define ft first
#define sd second
#define ll long long
#define pll pair<ll,ll>
const int N = 1e6 + 5;
const int M = 1e7 + 5;
const ll mod = 998244353;
const ll inf = 1e18;

ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res=binmul(res,x);x=binmul(x,x);ti >>= 1; x %= mod; res %= mod;} return res;}
ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); }
bool odd(ll n) { return (n % 2 == 1); }
bool even(ll n) { return (n % 2 == 0); }

ll n, k, x[N], y[N];
pll a[N];

const void solve() {
	cin >> n >> k;
	bool ok = 1;
	for (int i = 1; i <= n; ++ i) cin >> x[i] >> y[i], ok &= (y[i] == 0), a[i] = {x[i], y[i]};

	if (n <= 1000) {
	    vector <ll> v;
	    for (int i = 1; i < n; ++ i) {
	    	for (int j = i + 1; j <= n; ++ j) v.pb(abs(x[i] - x[j]) + abs(y[i] - y[j]));
	    }
	    sort(all(v));            
	    for (int i = 0; i < k; ++ i) cout << v[i] << "\n";
		return;
	}
    
		multiset<ll>st;
		sort(a + 1, a + n + 1);
		for (int i = 1; i <= n; ++ i) x[i] = a[i].ft, y[i] = a[i].sd;
		for (ll i = 1; i < n; ++ i) {
			for (int j = i + 1; j <= min(n, i + 5000); ++ j) {
				if (st.size() < k) st.insert(abs(x[i] - x[j]) + abs(y[i] - y[j]));
				else if (*st.rbegin() > abs(x[i] - x[j]) + abs(y[i] - y[j])) {
					st.erase(--st.end());
					st.insert(abs(x[i] - x[j]) + abs(y[i] - y[j]));
				}
			}	
		}            
		for (auto x : st) cout << x << "\n";
		return;



}

int main() {
   	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	srand(time(NULL));

	ll tt = 1;
	//cin >> tt; 

	while (tt --) solve();

	return 0;
}

Compilation message

road_construction.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization("O3")
      | 
road_construction.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization("unroll-loops")
      | 
road_construction.cpp:7: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    7 | #pragma comment(linker, "/stack:200000000")
      | 
road_construction.cpp: In function 'const void solve()':
road_construction.cpp:58:19: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   58 |     if (st.size() < k) st.insert(abs(x[i] - x[j]) + abs(y[i] - y[j]));
      |         ~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6988 KB Output is correct
2 Correct 59 ms 6984 KB Output is correct
3 Correct 38 ms 5108 KB Output is correct
4 Correct 41 ms 5056 KB Output is correct
5 Correct 55 ms 5832 KB Output is correct
6 Correct 21 ms 4556 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5683 ms 21052 KB Output is correct
2 Correct 5441 ms 22508 KB Output is correct
3 Correct 36 ms 4992 KB Output is correct
4 Correct 4954 ms 22248 KB Output is correct
5 Correct 4635 ms 22508 KB Output is correct
6 Correct 5191 ms 22616 KB Output is correct
7 Correct 5326 ms 21856 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3908 ms 8156 KB Output is correct
2 Correct 4618 ms 8160 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4431 ms 8152 KB Output is correct
5 Correct 4355 ms 8152 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3908 ms 8156 KB Output is correct
2 Correct 4618 ms 8160 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4431 ms 8152 KB Output is correct
5 Correct 4355 ms 8152 KB Output is correct
6 Correct 4707 ms 8148 KB Output is correct
7 Correct 4070 ms 8160 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3937 ms 8156 KB Output is correct
11 Correct 3959 ms 8160 KB Output is correct
12 Correct 3998 ms 8156 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6988 KB Output is correct
2 Correct 59 ms 6984 KB Output is correct
3 Correct 38 ms 5108 KB Output is correct
4 Correct 41 ms 5056 KB Output is correct
5 Correct 55 ms 5832 KB Output is correct
6 Correct 21 ms 4556 KB Output is correct
7 Correct 3221 ms 17124 KB Output is correct
8 Correct 3099 ms 19160 KB Output is correct
9 Correct 52 ms 5044 KB Output is correct
10 Correct 3059 ms 18528 KB Output is correct
11 Correct 3970 ms 18396 KB Output is correct
12 Correct 2041 ms 19144 KB Output is correct
13 Correct 2294 ms 17724 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6988 KB Output is correct
2 Correct 59 ms 6984 KB Output is correct
3 Correct 38 ms 5108 KB Output is correct
4 Correct 41 ms 5056 KB Output is correct
5 Correct 55 ms 5832 KB Output is correct
6 Correct 21 ms 4556 KB Output is correct
7 Correct 5683 ms 21052 KB Output is correct
8 Correct 5441 ms 22508 KB Output is correct
9 Correct 36 ms 4992 KB Output is correct
10 Correct 4954 ms 22248 KB Output is correct
11 Correct 4635 ms 22508 KB Output is correct
12 Correct 5191 ms 22616 KB Output is correct
13 Correct 5326 ms 21856 KB Output is correct
14 Correct 3908 ms 8156 KB Output is correct
15 Correct 4618 ms 8160 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 4431 ms 8152 KB Output is correct
18 Correct 4355 ms 8152 KB Output is correct
19 Correct 4707 ms 8148 KB Output is correct
20 Correct 4070 ms 8160 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 3937 ms 8156 KB Output is correct
24 Correct 3959 ms 8160 KB Output is correct
25 Correct 3998 ms 8156 KB Output is correct
26 Correct 3221 ms 17124 KB Output is correct
27 Correct 3099 ms 19160 KB Output is correct
28 Correct 52 ms 5044 KB Output is correct
29 Correct 3059 ms 18528 KB Output is correct
30 Correct 3970 ms 18396 KB Output is correct
31 Correct 2041 ms 19144 KB Output is correct
32 Correct 2294 ms 17724 KB Output is correct
33 Correct 6923 ms 26912 KB Output is correct
34 Correct 6790 ms 26908 KB Output is correct
35 Correct 6209 ms 26140 KB Output is correct
36 Correct 4586 ms 26940 KB Output is correct
37 Correct 4327 ms 26908 KB Output is correct
38 Correct 5135 ms 25748 KB Output is correct