Submission #946120

#TimeUsernameProblemLanguageResultExecution timeMemory
946120itslqRoad Construction (JOI21_road_construction)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int N, K, X, Y; vector<int> x, y; vector<vector<signed>> fenwick; void update(int i, int j1, bool b) { for (; i <= X; i += i & -i) { for (int j = j1; j <= Y; j += j & -j) { if (b) fenwick[i][j]++; else fenwick[i][j]--; } } } int query(int i, int j1) { int S = 0; for (; i > 0; i -= i & -i) { for (int j = j1; j > 0; j -= j & -j) { S += fenwick[i][j]; } } return S; } bool check(int d) { int x1, y1, S = 0, ia, ib, ic, id; vector<int> xdisc, ydisc; for (int i = 0; i < N; i++) { x1 = x[i]; y1 = y[i]; xdisc.push_back(x1 - y1 - d); xdisc.push_back(x1 - y1); xdisc.push_back(x1 - y1 + d); ydisc.push_back(x1 + y1 - d); ydisc.push_back(x1 + y1); ydisc.push_back(x1 + y1 + d); } sort(xdisc.begin(), xdisc.end()); sort(ydisc.begin(), ydisc.end()); xdisc.erase(unique(xdisc.begin(), xdisc.end()), xdisc.end()); ydisc.erase(unique(ydisc.begin(), ydisc.end()), ydisc.end()); X = xdisc.size(); Y = ydisc.size(); fenwick = vector<vector<int>>(X + 1, vector<int>(Y + 1)); for (int i = 0; i < N; i++) { x1 = x[i]; y1 = y[i]; ia = lower_bound(xdisc.begin(), xdisc.end(), x1 - y1) - xdisc.begin() + 1; ib = lower_bound(ydisc.begin(), ydisc.end(), x1 + y1) - ydisc.begin() + 1; if ((S += query(ia, ib)) >= K) return true; ia = lower_bound(xdisc.begin(), xdisc.end(), x1 - y1 - d) - xdisc.begin() + 1; ib = lower_bound(xdisc.begin(), xdisc.end(), x1 - y1 + d) - xdisc.begin() + 1; ic = lower_bound(ydisc.begin(), ydisc.end(), x1 + y1 - d) - ydisc.begin() + 1; id = lower_bound(ydisc.begin(), ydisc.end(), x1 + y1 + d) - ydisc.begin() + 1; update(ia, ic, 1); update(ib + 1, ic, 0); update(ia, id + 1, 0); update(ib + 1, id + 1, 1); } return false; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> K; K = 1; //REMOVE x.resize(N); y.resize(N); for (int i = 0; i < N; i++) cin >> x[i] >> y[i]; int l = 0, r = 4e9, m, ans; while (l <= r) { m = (l + r) >> 1; if (check(m)) { ans = m; r = --m; } else { l = ++m; } } cout << ans; return 0; }

Compilation message (stderr)

road_construction.cpp: In function 'bool check(long long int)':
road_construction.cpp:54:60: error: no match for 'operator=' (operand types are 'std::vector<std::vector<int> >' and 'std::vector<std::vector<long long int> >')
   54 |     fenwick = vector<vector<int>>(X + 1, vector<int>(Y + 1));
      |                                                            ^
In file included from /usr/include/c++/10/vector:72,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from road_construction.cpp:1:
/usr/include/c++/10/bits/vector.tcc:198:5: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >]'
  198 |     vector<_Tp, _Alloc>::
      |     ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:199:42: note:   no known conversion for argument 1 from 'std::vector<std::vector<long long int> >' to 'const std::vector<std::vector<int> >&'
  199 |     operator=(const vector<_Tp, _Alloc>& __x)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from road_construction.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:709:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >]'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:709:26: note:   no known conversion for argument 1 from 'std::vector<std::vector<long long int> >' to 'std::vector<std::vector<int> >&&'
  709 |       operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
      |                 ~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:730:7: note: candidate: 'std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >]'
  730 |       operator=(initializer_list<value_type> __l)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:730:46: note:   no known conversion for argument 1 from 'std::vector<std::vector<long long int> >' to 'std::initializer_list<std::vector<int> >'
  730 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~