| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1243798 | Matthewwww | Road Construction (JOI21_road_construction) | C++17 | Compilation error | 0 ms | 0 KiB |
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif
int dist (pair<int, int> a, pair<int, int> b) {
return max(abs(a.f-b.f), abs(a.s-b.s));
}
signed main (signed argc, char **argv) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<pair<int, int>> vt(n);
for (auto &i: vt) cin >> i.f >> i.s;
for (auto &i: vt) i = {i.f-i.s, i.f+i.s};
sort(vt.begin(), vt.end());
int len = 0;
for (int bt = 40; bt--;) {
int m = len+(1ll<<bt);
int cnt = 0;
set<pair<int, int>> st;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int upto = 0;
for (auto i: vt) {
while (pq.size() && pq.top().f < i.f-m) {
st.erase({vt[pq.top().s].s, pq.top().s});
pq.pop();
}
cnt += distance(st.lower_bound({i.s-m, 0}), st.upper_bound(i.s+m, n}));
if (cnt >= k) break;
st.insert({i.s, upto});
pq.push({i.f, upto++});
}
if (cnt < k) len = m;
}
vector<int> ans;
set<pair<int, int>> st;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int upto = 0;
for (auto i: vt) {
while (pq.size() && pq.top().f < i.f-len) {
st.erase({vt[pq.top().s].s, pq.top().s});
pq.pop();
}
for (auto j = st.lower_bound({i.s-len, 0}); j != st.upper_bound({i.s+len, n}); ++j)
ans.push_back(dist(i, vt[(*j).s]));
st.insert({i.s, upto});
pq.push({i.f, upto++});
}
int left = k-(int)ans.size();
sort(ans.begin(), ans.end());
for (int i: ans) cout << i << "\n";
while (left--) cout << len+1 << "\n";
}
/*
*
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┗━┓ ┏━┛ + +
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the llama protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/
//thanks cindy
Compilation message (stderr)
road_construction.cpp: In function 'int main(int, char**)':
road_construction.cpp:39:92: error: expected ')' before '}' token
39 | cnt += distance(st.lower_bound({i.s-m, 0}), st.upper_bound(i.s+m, n}));
| ~ ^
| )
road_construction.cpp:39:93: error: expected primary-expression before ')' token
39 | cnt += distance(st.lower_bound({i.s-m, 0}), st.upper_bound(i.s+m, n}));
| ^
road_construction.cpp:41:36: error: 'i' was not declared in this scope
41 | st.insert({i.s, upto});
| ^
road_construction.cpp:41:34: error: no matching function for call to 'std::set<std::pair<long long int, long long int> >::insert(<brace-enclosed initializer list>)'
41 | st.insert({i.s, upto});
| ~~~~~~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/11/set:61,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:87,
from road_construction.cpp:3:
/usr/include/c++/11/bits/stl_set.h:566:9: note: candidate: 'template<class _InputIterator> void std::set<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >]'
566 | insert(_InputIterator __first, _InputIterator __last)
| ^~~~~~
/usr/include/c++/11/bits/stl_set.h:566:9: note: template argument deduction/substitution failed:
road_construction.cpp:41:34: note: candidate expects 2 arguments, 1 provided
41 | st.insert({i.s, upto});
| ~~~~~~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/11/set:61,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:87,
from road_construction.cpp:3:
/usr/include/c++/11/bits/stl_set.h:509:7: note: candidate: 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other = std::allocator<std::pair<long long int, long long int> >; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key> = __gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::rebind<std::pair<long long int, long long int> >; typename _Alloc::value_type = std::pair<long long int, long long int>; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<long long int, long long int>]'
509 | insert(const value_type& __x)
| ^~~~~~
/usr/include/c++/11/bits/stl_set.h:509:32: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<long long int, long long int>&'}
509 | insert(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_set.h:518:7: note: candidate: 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other = std::allocator<std::pair<long long int, long long int> >; typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key> = __gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::rebind<std::pair<long long int, long long int> >; typename _Alloc::value_type = std::pair<long long int, long long int>; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<long long int, long long int>]'
518 | insert(value_type&& __x)
| ^~~~~~
/usr/include/c++/11/bits/stl_set.h:518:27: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::set<std::pair<long long int, long long int> >::value_type&&' {aka 'std::pair<long long int, long long int>&&'}
518 | insert(value_type&& __x)
| ~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_set.h:546:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::const_iterator, const value_type&) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<long long int, long long int>]'
546 | insert(const_iterator __position, const value_type& __x)
| ^~~~~~
/usr/include/c++/11/bits/stl_set.h:546:7: note: candidate expects 2 arguments, 1 provided
/usr/include/c++/11/bits/stl_set.h:551:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::const_iterator, std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<long long int, long long int>]'
551 | insert(const_iterator __position, value_type&& __x)
| ^~~~~~
/usr/include/c++/11/bits/stl_set.h:551:7: note: candidate expects 2 arguments, 1 provided
/usr/include/c++/11/bits/stl_set.h:578:7: note: candidate: 'void std::set<_Key, _Compare, _Alloc>::insert(std::initializer_list<_Tp>) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >]'
578 | insert(initializer_list<value_type> __l)
| ^~~~~~
/usr/include/c++/11/bits/stl_set.h:578:43: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::initializer_list<std::pair<long long int, long long int> >'
578 | insert(initializer_list<value_type> __l)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_set.h:598:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::insert_return_type std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::node_type&&) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::insert_return_type = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::insert_return_type; std::set<_Key, _Compare, _Alloc>::node_type = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::node_type]'
598 | insert(node_type&& __nh)
| ^~~~~~
/usr/include/c++/11/bits/stl_set.h:598:26: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::set<std::pair<long long int, long long int> >::node_type&&' {aka 'std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::node_type&&'}
598 | insert(node_type&& __nh)
| ~~~~~~~~~~~~^~~~
/usr/include/c++/11/bits/stl_set.h:603:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::const_iterator, std::set<_Key, _Compare, _Alloc>::node_type&&) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::node_type = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::node_type]'
603 | insert(const_iterator __hint, node_type&& __nh)
| ^~~~~~
/usr/include/c++/11/bits/stl_set.h:603:7: note: candidate expects 2 arguments, 1 provided
road_construction.cpp:42:32: error: no matching function for call to 'std::priority_queue<std::pair<long long int, long long int>, std::vector<std::pair<long long int, long long int> >, std::greater<std::pair<long long int, long long int> > >::push(<brace-enclosed initializer list>)'
42 | pq.push({i.f, upto++});
| ~~~~~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/queue:64,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:86,
from road_construction.cpp:3:
/usr/include/c++/11/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::pair<long long int, long long int>; _Sequence = std::vector<std::pair<long long int, long long int> >; _Compare = std::greater<std::pair<long long int, long long int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::pair<long long int, long long int>]'
640 | push(const value_type& __x)
| ^~~~
/usr/include/c++/11/bits/stl_queue.h:640:30: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<long long int, long long int>&'}
640 | push(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::pair<long long int, long long int>; _Sequence = std::vector<std::pair<long long int, long long int> >; _Compare = std::greater<std::pair<long long int, long long int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::pair<long long int, long long int>]'
648 | push(value_type&& __x)
| ^~~~
/usr/include/c++/11/bits/stl_queue.h:648:25: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::pair<long long int, long long int>, std::vector<std::pair<long long int, long long int> >, std::greater<std::pair<long long int, long long int> > >::value_type&&' {aka 'std::pair<long long int, long long int>&&'}
648 | push(value_type&& __x)
| ~~~~~~~~~~~~~^~~
road_construction.cpp:44:21: error: 'cnt' was not declared in this scope; did you mean 'int'?
44 | if (cnt < k) len = m;
| ^~~
| int
road_construction.cpp:44:36: error: 'm' was not declared in this scope
44 | if (cnt < k) len = m;
| ^
road_construction.cpp: At global scope:
road_construction.cpp:50:9: error: expected unqualified-id before 'for'
50 | for (auto i: vt) {
| ^~~
road_construction.cpp:60:20: error: 'k' was not declared in this scope
60 | int left = k-(int)ans.size();
| ^
road_construction.cpp:61:13: error: expected constructor, destructor, or type conversion before '(' token
61 | sort(ans.begin(), ans.end());
| ^
road_construction.cpp:62:9: error: expected unqualified-id before 'for'
62 | for (int i: ans) cout << i << "\n";
| ^~~
road_construction.cpp:63:9: error: expected unqualified-id before 'while'
63 | while (left--) cout << len+1 << "\n";
| ^~~~~
road_construction.cpp:64:1: error: expected declaration before '}' token
64 | }
| ^