oj.uz

Submission #387741

# Submission time Handle Problem Language Result Execution time Memory
387741 2021-04-09T07:02:22 Z abc864197532 Road Construction (JOI21_road_construction) C++17
Compilation error
 0 ms 0 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, N = 300001, K = 111;

struct Pt {
    lli x, y, idx;
    Pt (lli _x = 0, lli _y = 0) : x(_x), y(_y) {}
    bool operator < (const Pt &o) {
        return x < o.x;
    }
};

struct cmp {
    bool operator () (Pt a, Pt b) {
        if (a.y == b.y) return a.idx < b.idx;
        return a.y < b.y;
    }
};

int bit[N];

void reset() {
    for (int i = 0; i < N; ++i) bit[i] = 0;
}

void add(int p, int v) {
    for (int i = p; i < N; i += i & (-i)) bit[i] += v;
}

int query(int p) {
    int ans = 0;
    for (int i = p; i > 0; i -= i & (-i)) ans += bit[i];
    return ans;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector <Pt> a;
    for (int i = 0, x, y; i < n; ++i) {
        cin >> x >> y;
        a.pb(Pt(x + y, x - y));
        a.back().idx = i;
    }
    vector <lli> y_idx;
    for (int i = 0; i < n; ++i) y_idx.pb(a[i].y);
    sort(all(y_idx));
    y_idx.resize(unique(all(y_idx)) - y_idx.begin());
    auto get = [&](lli x) {
        return lower_bound(all(y_idx), x) - y_idx.begin() + 5;
    };
    sort(all(a));
    auto chk = [&](lli d) {
        /*
         * 2 4 8 9 15
         * 4 9
         */
        reset();
        lli ans = 0;
        for (int i = 0, j = 0; i < n; ++i) {
            while (j < n && a[j].x + d < a[i].x) add(get(a[j++].y), -1);
            ans += query(get(a[i].y + d + 1) - 1) - query(get(a[i].y - d) - 1);
            add(get(a[i].y), 1);
        }
        return ans;
    };
    lli l = 0, r = 2e9 + 87;
    while (r - l > 1) {
        ((chk(l + r >> 1)) < k ? l : r) = l + r >> 1;
    }
    int d = l;
    l = 0, r = 2e9 + 87;
    while (r - l > 1) {
        ((chk(l + r >> 1)) >= k ? r : l) = l + r >> 1;
    }
    vector <int> ans;
    set <Pt, cmp> s;
    for (int i = 0, j = 0; i < n; ++i) {
        while (j < n && a[j].x + d < a[i].x) s.erase(a[j++]);
        for (auto it = s.lower_bound(Pt(0, a[i].y - d)); it != s.end() && it->y <= a[i].y + d; ++it) {
            ans.pb(max(a[i].x - it->x, abs(it->y - a[i].y)));
        }
        s.insert(a[i]);
    }
    sort(all(ans));
    for (int i = 0; i < k; ++i) {
        if (i < ans.size()) cout << ans[i] << '\n';
        else cout << r << '\n';
    }
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:94:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         ((chk(l + r >> 1)) < k ? l : r) = l + r >> 1;
      |               ~~^~~
road_construction.cpp:94:45: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         ((chk(l + r >> 1)) < k ? l : r) = l + r >> 1;
      |                                           ~~^~~
road_construction.cpp:99:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |         ((chk(l + r >> 1)) >= k ? r : l) = l + r >> 1;
      |               ~~^~~
road_construction.cpp:99:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |         ((chk(l + r >> 1)) >= k ? r : l) = l + r >> 1;
      |                                            ~~^~~
road_construction.cpp:112:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         if (i < ans.size()) cout << ans[i] << '\n';
      |             ~~^~~~~~~~~~~~
In file included from /usr/include/c++/9/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:81,
                 from road_construction.cpp:1:
/usr/include/c++/9/bits/stl_tree.h: In instantiation of 'static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = Pt; _Val = Pt; _KeyOfValue = std::_Identity<Pt>; _Compare = cmp; _Alloc = std::allocator<Pt>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<Pt>*]':
/usr/include/c++/9/bits/stl_tree.h:1997:37:   required from 'std::pair<std::_Rb_tree_iterator<_Val>, std::_Rb_tree_iterator<_Val> > std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::equal_range(const _Key&) [with _Key = Pt; _Val = Pt; _KeyOfValue = std::_Identity<Pt>; _Compare = cmp; _Alloc = std::allocator<Pt>]'
/usr/include/c++/9/bits/stl_tree.h:2534:32:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::erase(const _Key&) [with _Key = Pt; _Val = Pt; _KeyOfValue = std::_Identity<Pt>; _Compare = cmp; _Alloc = std::allocator<Pt>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type = long unsigned int]'
/usr/include/c++/9/bits/stl_set.h:685:30:   required from 'std::set<_Key, _Compare, _Alloc>::size_type std::set<_Key, _Compare, _Alloc>::erase(const key_type&) [with _Key = Pt; _Compare = cmp; _Alloc = std::allocator<Pt>; std::set<_Key, _Compare, _Alloc>::size_type = long unsigned int; std::set<_Key, _Compare, _Alloc>::key_type = Pt]'
road_construction.cpp:104:60:   required from here
/usr/include/c++/9/bits/stl_tree.h:780:8: error: static assertion failed: comparison object must be invocable as const
  780 |        is_invocable_v<const _Compare&, const _Key&, const _Key&>,
      |        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~