oj.uz

Submission #682480

# Submission time Handle Problem Language Result Execution time Memory
682480 2023-01-16T09:28:07 Z vjudge1 Road Construction (JOI21_road_construction) C++17
100 / 100
 3982 ms 21880 KB 
#include "bits/stdc++.h"
using namespace std;

// #define ORD_SET
// #define ROPE
#ifdef ORD_SET
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    using namespace __gnu_pbds;
    template<typename T>
    using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif
#ifdef ROPE
    #include <ext/rope>
    using namespace __gnu_cxx;
#endif        

// #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 ll = long long;
using ld = long double;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (ll)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
// #define ll int
void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
void NotInteractive() { ios_base::sync_with_stdio(false); cin.tie(NULL); }
void pre(ll a) { cout<<fixed<<setprecision(a); }
ll bit(ll x) { return __builtin_popcountll(x); }
ll binpow(ll x, ll y, ll z) { ll pow = 1; while(y) { if(y&1) pow *= x, pow %= z; x *= x, x %= z; y >>= 1; } return pow; }
template<typename T> T gcd(T a, T b) { if(b==0) return a; return gcd(b, a%b); }
template<typename T> T lcm(T a, T b) { return a/gcd(a, b)*b; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct sn { ll l, r, x; }; // a.swap(b)
ll B = 316;
const ll mod = (ll)1e9+7;
const ll inf = (ll)1e18+7;
const ll MX = LLONG_MAX;
const ll MN = LLONG_MIN;
const ld P = acos(-1.0);
const ll N = (ll)3e5+5;
ll x[N], y[N];

void kigash() {
    ll n, k;
    cin>>n>>k;
    vector<pair<ll, ll>> v;
    for(ll i=1; i<=n; i++) cin>>x[i]>>y[i], v.pb({x[i], y[i]});
    sort(all(v));
    multiset<ll> ans;
    for(ll i=0; i<n; i++) {
        ll cnt = (ll)500000000/n;
        for(ll j=i+1; j<n && cnt; j++) {
            if(sz(ans)<k) ans.insert(abs(v[i].ff-v[j].ff)+abs(v[i].ss-v[j].ss));
            else if(*ans.rbegin()>abs(v[i].ff-v[j].ff)+abs(v[i].ss-v[j].ss)) ans.erase(prev(ans.end())), ans.insert(abs(v[i].ff-v[j].ff)+abs(v[i].ss-v[j].ss));
            cnt--;
        }
    }
    for(auto to: ans) cout<<to<<"\n";
    return;
}

signed main(/**/) {
    // freopen("");
    NotInteractive();
    // precalc();
    
    ll tt = 1;
    // cin>>tt;
    for(ll i=1; i<=tt; i++) kigash();
    
    exit(0);
}

Compilation message

road_construction.cpp: In function 'void freopen(std::string)':
road_construction.cpp:31:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
      |                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:31:75: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
      |                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 14668 KB Output is correct
2 Correct 266 ms 14652 KB Output is correct
3 Correct 197 ms 14716 KB Output is correct
4 Correct 126 ms 14644 KB Output is correct
5 Correct 198 ms 13612 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 3200 ms 21076 KB Output is correct
2 Correct 3243 ms 21052 KB Output is correct
3 Correct 89 ms 14528 KB Output is correct
4 Correct 2973 ms 20904 KB Output is correct
5 Correct 2645 ms 21120 KB Output is correct
6 Correct 2724 ms 21116 KB Output is correct
7 Correct 2754 ms 20280 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1861 ms 8304 KB Output is correct
2 Correct 1852 ms 8196 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1921 ms 8192 KB Output is correct
5 Correct 1881 ms 8200 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1861 ms 8304 KB Output is correct
2 Correct 1852 ms 8196 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1921 ms 8192 KB Output is correct
5 Correct 1881 ms 8200 KB Output is correct
6 Correct 1869 ms 8180 KB Output is correct
7 Correct 1846 ms 8228 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1925 ms 8248 KB Output is correct
11 Correct 1922 ms 8252 KB Output is correct
12 Correct 1874 ms 8160 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 14668 KB Output is correct
2 Correct 266 ms 14652 KB Output is correct
3 Correct 197 ms 14716 KB Output is correct
4 Correct 126 ms 14644 KB Output is correct
5 Correct 198 ms 13612 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 3250 ms 17196 KB Output is correct
8 Correct 3403 ms 17124 KB Output is correct
9 Correct 135 ms 14720 KB Output is correct
10 Correct 3408 ms 16488 KB Output is correct
11 Correct 3982 ms 16448 KB Output is correct
12 Correct 2345 ms 17128 KB Output is correct
13 Correct 2570 ms 15592 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 14668 KB Output is correct
2 Correct 266 ms 14652 KB Output is correct
3 Correct 197 ms 14716 KB Output is correct
4 Correct 126 ms 14644 KB Output is correct
5 Correct 198 ms 13612 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 3200 ms 21076 KB Output is correct
8 Correct 3243 ms 21052 KB Output is correct
9 Correct 89 ms 14528 KB Output is correct
10 Correct 2973 ms 20904 KB Output is correct
11 Correct 2645 ms 21120 KB Output is correct
12 Correct 2724 ms 21116 KB Output is correct
13 Correct 2754 ms 20280 KB Output is correct
14 Correct 1861 ms 8304 KB Output is correct
15 Correct 1852 ms 8196 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1921 ms 8192 KB Output is correct
18 Correct 1881 ms 8200 KB Output is correct
19 Correct 1869 ms 8180 KB Output is correct
20 Correct 1846 ms 8228 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 1925 ms 8248 KB Output is correct
24 Correct 1922 ms 8252 KB Output is correct
25 Correct 1874 ms 8160 KB Output is correct
26 Correct 3250 ms 17196 KB Output is correct
27 Correct 3403 ms 17124 KB Output is correct
28 Correct 135 ms 14720 KB Output is correct
29 Correct 3408 ms 16488 KB Output is correct
30 Correct 3982 ms 16448 KB Output is correct
31 Correct 2345 ms 17128 KB Output is correct
32 Correct 2570 ms 15592 KB Output is correct
33 Correct 3455 ms 21880 KB Output is correct
34 Correct 3336 ms 21868 KB Output is correct
35 Correct 3416 ms 21052 KB Output is correct
36 Correct 2306 ms 21668 KB Output is correct
37 Correct 2254 ms 21820 KB Output is correct
38 Correct 2575 ms 20288 KB Output is correct