oj.uz

Submission #876221

# Submission time Handle Problem Language Result Execution time Memory
876221 2023-11-21T12:51:18 Z Regulus Road Construction (JOI21_road_construction) C++17
32 / 100
 918 ms 11024 KB 
#include <bits/stdc++.h>            // pA
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cerr << #x << " = " << (x) << ' '
#define endl cerr << '\n'
#define all(v) (v).begin(), (v).end()
#define SZ(v) (ll)(v).size()
#define lowbit(x) (x)&-(x)
#define pb emplace_back
#define F first
#define S second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

const int N = 2e5+5;
const ll INF = 1e18;
ll n, Q;
pll p[N];
multiset<pll> st;
vector<ll> v;

//#define test

inline bool chk(ll w)
{
    ll i, L=1, x, y;

    st.clear(), v.clear();
    for (i=1; i <= n; ++i)
    {
        while (p[i].F-p[L].F > w)
        {
            #ifdef test
            debug(i), debug(L), debug(w), endl;
            #endif
            st.erase(st.find({p[L].S, p[L].F}));
            ++L;
        }

        for (auto it = st.lower_bound({p[i].S, -INF}); it != st.end(); ++it)
        {
            x = it->S, y = it->F;
            if (y-p[i].S > w) break;
            v.pb(max(abs(x-p[i].F), abs(y-p[i].S)));
            if (SZ(v) >= Q) return 1;
        }
        auto it = st.lower_bound({p[i].S, -INF});
        if (it != st.begin())
        {
            --it;
            for ( ; ; --it)
            {
                x = it->S, y = it->F;
                if (p[i].S-y > w) break;
                v.pb(max(abs(x-p[i].F), abs(y-p[i].S)));
                if (SZ(v) >= Q) return 1;
                if (it == st.begin()) break;
            }
        }
        st.insert({p[i].S, p[i].F});

        #ifdef test
        debug(i), endl;
        for (auto x : st) cerr << x.F << ' ' << x.S << '\n';
        #endif
    }
    return 0;
}

int main(void)
{ IO
    ll i, lb, mid, ub, x, y;

    cin >> n >> Q;
    for (i=1; i <= n; ++i) cin >> x >> y, p[i] = {x+y, x-y};

    sort(p+1, p+n+1);
    #ifndef test
    lb = 0, ub = 1e18;
    while (lb < ub)
    {
        mid = (lb+ub)>>1;
        if (chk(mid)) ub = mid;
        else lb = mid + 1;
    }

    chk(lb-1);
    sort(all(v));
    for (i=0; i < min(Q, SZ(v)); ++i) cout << v[i] << '\n';
    for (i=0; i < max(Q-SZ(v), 0LL); ++i) cout << lb << '\n';

    #else
    endl;
    for (i=1; i <= n; ++i) debug(p[i].F), debug(p[i].S), endl;

    endl;
    chk(2);
    endl;
    for (ll x : v) debug(x), endl;
    #endif


    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 5148 KB Output is correct
2 Correct 196 ms 5068 KB Output is correct
3 Correct 136 ms 5072 KB Output is correct
4 Correct 131 ms 5132 KB Output is correct
5 Correct 142 ms 4032 KB Output is correct
6 Correct 3 ms 348 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 9564 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 44 ms 11024 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 44 ms 11024 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 148 ms 5148 KB Output is correct
2 Correct 196 ms 5068 KB Output is correct
3 Correct 136 ms 5072 KB Output is correct
4 Correct 131 ms 5132 KB Output is correct
5 Correct 142 ms 4032 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 918 ms 8604 KB Output is correct
8 Correct 899 ms 8612 KB Output is correct
9 Correct 139 ms 5140 KB Output is correct
10 Correct 451 ms 7872 KB Output is correct
11 Correct 317 ms 7828 KB Output is correct
12 Correct 337 ms 8628 KB Output is correct
13 Correct 412 ms 7164 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 5148 KB Output is correct
2 Correct 196 ms 5068 KB Output is correct
3 Correct 136 ms 5072 KB Output is correct
4 Correct 131 ms 5132 KB Output is correct
5 Correct 142 ms 4032 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Runtime error 27 ms 9564 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -