Submission #876216

#	Time	Username	Problem	Language	Result	Execution time	Memory
876216		Regulus	Road Construction (JOI21_road_construction)	C++17	Compilation error	0 ms	0 KiB

road_construction

#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 (v.size() >= 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 (v.size() >= 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, (ll)v.size()); ++i) cout << v[i] << '\n';
    for (i=0; i < max(Q-v.size(), 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;
}

Compilation message (stderr)

road_construction.cpp: In function 'bool chk(ll)':
road_construction.cpp:45:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   45 |             if (v.size() >= Q) return 1;
      |                 ~~~~~~~~~^~~~
road_construction.cpp:56:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   56 |                 if (v.size() >= Q) return 1;
      |                     ~~~~~~~~~^~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:90:38: error: no matching function for call to 'max(long long unsigned int, long long int)'
   90 |     for (i=0; i < max(Q-v.size(), 0LL); ++i) cout << lb << '\n';
      |                                      ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from road_construction.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
road_construction.cpp:90:38: note:   deduced conflicting types for parameter 'const _Tp' ('long long unsigned int' and 'long long int')
   90 |     for (i=0; i < max(Q-v.size(), 0LL); ++i) cout << lb << '\n';
      |                                      ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from road_construction.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
road_construction.cpp:90:38: note:   deduced conflicting types for parameter 'const _Tp' ('long long unsigned int' and 'long long int')
   90 |     for (i=0; i < max(Q-v.size(), 0LL); ++i) cout << lb << '\n';
      |                                      ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from road_construction.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
road_construction.cpp:90:38: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long unsigned int'
   90 |     for (i=0; i < max(Q-v.size(), 0LL); ++i) cout << lb << '\n';
      |                                      ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from road_construction.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
road_construction.cpp:90:38: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long unsigned int'
   90 |     for (i=0; i < max(Q-v.size(), 0LL); ++i) cout << lb << '\n';
      |                                      ^