제출 #500527

#제출 시각아이디문제언어결과실행 시간메모리
500527MazaalaiHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h> #define pb push_back #define ff first #define ss second #define ALL(x) x.begin(),x.end() using namespace std; using ll = long long; using PII = pair <int, int>; using VI = vector <int>; using VVI = vector <VI>; using VPI = vector <PII>; struct Node { int max, maxInv; Node() { max = -1; maxInv = -1; } }; const int N = 2e5 + 5; const int M = 4 * N; int n, m; VPI addNum; int nums[N], queries[N], K[N]; Node node[M]; void build(int l, int r, int head) { if (l == r) { node[head].max = nums[l]; return; } int mid = (l+r)>>1; build(l, mid, head*2+1); build(mid+1, r, head*2+2); node[head].max = max(node[head*2+1].max, node[head*2+2].max); int curMax = nums[l]; for (int i = l+1; i <= r; i++) { if (nums[i] >= curMax) curMax = nums[i]; else node[head].maxInv = max(node[head].maxInv, curMax+nums[i]); } } void update(int l, int r, int id, int val, int head) { if (l == r) { node[head].max = val; return; } int mid = (l+r)>>1; if (id <= mid) update(l, mid, id, val, head*2+1); else update(mid+1, r, id, val, head*2+2); node[head].max = max(node[head*2+1].max, node[head*2+2].max); } int query(int l, int r, int L, int R, int head) { if (l > R || L > r) return -1; if (L <= l && r <= R) return node[head].max; int mid = (l+r)>>1; return max( query(l, mid, L, R, head*2+1), query(mid+1, r, L, R, head*2+2) ); } set <VI> allCheck;// lMax, id, l, r; int dfs(int l, int r, int L, int R, int id, int head) { // return insideMax; if (L <= l && r <= R) { queries[id] = max(queries[id], node[head].maxInv); return node[head].max; } int mid = (l+r)>>1; if (R <= mid) return dfs(l, mid, L, R, id, head*2+1); if (mid+1 <= L) return dfs(mid+1, r, L, R, id, head*2+2); int lMax = dfs(l, mid, L, R, id, head*2+1); // lRange = max(mid+1, L), rRange = min(r, R); allCheck.insert({lMax, id, max(mid+1, L), rRange = min(r, R)}); lMax = max(lMax, dfs(mid+1, r, L, R, id, head*2+2)); return lMax; } signed main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> nums[i]; addNum.pb({nums[i], i}); } build(1, n, 0); sort(ALL(addNum)); memset(queries, -1, sizeof(queries)); int l, r; for (int i = 1; i <= m; i++) { cin >> l >> r >> K[i]; dfs(1, n, l, r, i, 0); } for (int i = 0; i < M; i++) node[i].max = -1; int addId = 0, lMax, id, L, R, mid, head; VI tmp; while(!allCheck.empty()) { auto it = allCheck.begin(); tmp = *it; allCheck.erase(it); lMax = tmp[0]; id = tmp[1]; l = tmp[2]; r = tmp[3]; while (addId < addNum.size() && lMax > addNum[addId].ff) { int num, I; tie(num, I) = addNum[addId++]; update(1, n, I, num, 0); } if (lMax * 2 - 1 <= queries[id]) continue; int cur = query(1, n, l, r, 0); cur = (cur == -1 ? -1 : lMax+cur); queries[id] = max(queries[id], cur); } for (int i = 1; i <= m; i++) cout << (queries[i] <= K[i] ? 1 : 0) << '\n'; }

컴파일 시 표준 에러 (stderr) 메시지

sortbooks.cpp: In function 'int dfs(int, int, int, int, int, int)':
sortbooks.cpp:72:44: error: 'rRange' was not declared in this scope
   72 |  allCheck.insert({lMax, id, max(mid+1, L), rRange = min(r, R)});
      |                                            ^~~~~~
sortbooks.cpp:72:63: error: no matching function for call to 'std::set<std::vector<int> >::insert(<brace-enclosed initializer list>)'
   72 |  allCheck.insert({lMax, id, max(mid+1, L), rRange = min(r, R)});
      |                                                               ^
In file included from /usr/include/c++/10/set:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from sortbooks.cpp:1:
/usr/include/c++/10/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::vector<int>; _Compare = std::less<std::vector<int> >; _Alloc = std::allocator<std::vector<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::vector<int>, std::vector<int>, std::_Identity<std::vector<int> >, std::less<std::vector<int> >, std::allocator<std::vector<int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = std::vector<int>]'
  509 |       insert(const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/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::vector<int>&'}
  509 |       insert(const value_type& __x)
      |              ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/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::vector<int>; _Compare = std::less<std::vector<int> >; _Alloc = std::allocator<std::vector<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::vector<int>, std::vector<int>, std::_Identity<std::vector<int> >, std::less<std::vector<int> >, std::allocator<std::vector<int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = std::vector<int>]'
  518 |       insert(value_type&& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:518:27: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::set<std::vector<int> >::value_type&&' {aka 'std::vector<int>&&'}
  518 |       insert(value_type&& __x)
      |              ~~~~~~~~~~~~~^~~
/usr/include/c++/10/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::vector<int>; _Compare = std::less<std::vector<int> >; _Alloc = std::allocator<std::vector<int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::vector<int>, std::vector<int>, std::_Identity<std::vector<int> >, std::less<std::vector<int> >, std::allocator<std::vector<int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::vector<int>, std::vector<int>, std::_Identity<std::vector<int> >, std::less<std::vector<int> >, std::allocator<std::vector<int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = std::vector<int>]'
  546 |       insert(const_iterator __position, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:546:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/10/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::vector<int>; _Compare = std::less<std::vector<int> >; _Alloc = std::allocator<std::vector<int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::vector<int>, std::vector<int>, std::_Identity<std::vector<int> >, std::less<std::vector<int> >, std::allocator<std::vector<int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::vector<int>, std::vector<int>, std::_Identity<std::vector<int> >, std::less<std::vector<int> >, std::allocator<std::vector<int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = std::vector<int>]'
  551 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:551:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_set.h:566:2: note: candidate: 'template<class _InputIterator> void std::set<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Key = std::vector<int>; _Compare = std::less<std::vector<int> >; _Alloc = std::allocator<std::vector<int> >]'
  566 |  insert(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~
/usr/include/c++/10/bits/stl_set.h:566:2: note:   template argument deduction/substitution failed:
sortbooks.cpp:72:63: note:   candidate expects 2 arguments, 1 provided
   72 |  allCheck.insert({lMax, id, max(mid+1, L), rRange = min(r, R)});
      |                                                               ^
In file included from /usr/include/c++/10/set:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from sortbooks.cpp:1:
/usr/include/c++/10/bits/stl_set.h:578:7: note: candidate: 'void std::set<_Key, _Compare, _Alloc>::insert(std::initializer_list<_Tp>) [with _Key = std::vector<int>; _Compare = std::less<std::vector<int> >; _Alloc = std::allocator<std::vector<int> >]'
  578 |       insert(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:578:43: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::initializer_list<std::vector<int> >'
  578 |       insert(initializer_list<value_type> __l)
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/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::vector<int>; _Compare = std::less<std::vector<int> >; _Alloc = std::allocator<std::vector<int> >; std::set<_Key, _Compare, _Alloc>::insert_return_type = std::_Rb_tree<std::vector<int>, std::vector<int>, std::_Identity<std::vector<int> >, std::less<std::vector<int> >, std::allocator<std::vector<int> > >::insert_return_type; std::set<_Key, _Compare, _Alloc>::node_type = std::_Rb_tree<std::vector<int>, std::vector<int>, std::_Identity<std::vector<int> >, std::less<std::vector<int> >, std::allocator<std::vector<int> > >::node_type]'
  598 |       insert(node_type&& __nh)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:598:26: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::set<std::vector<int> >::node_type&&' {aka 'std::_Rb_tree<std::vector<int>, std::vector<int>, std::_Identity<std::vector<int> >, std::less<std::vector<int> >, std::allocator<std::vector<int> > >::node_type&&'}
  598 |       insert(node_type&& __nh)
      |              ~~~~~~~~~~~~^~~~
/usr/include/c++/10/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::vector<int>; _Compare = std::less<std::vector<int> >; _Alloc = std::allocator<std::vector<int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::vector<int>, std::vector<int>, std::_Identity<std::vector<int> >, std::less<std::vector<int> >, std::allocator<std::vector<int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::vector<int>, std::vector<int>, std::_Identity<std::vector<int> >, std::less<std::vector<int> >, std::allocator<std::vector<int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::node_type = std::_Rb_tree<std::vector<int>, std::vector<int>, std::_Identity<std::vector<int> >, std::less<std::vector<int> >, std::allocator<std::vector<int> > >::node_type]'
  603 |       insert(const_iterator __hint, node_type&& __nh)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:603:7: note:   candidate expects 2 arguments, 1 provided
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:103:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   while (addId < addNum.size() && lMax > addNum[addId].ff) {
      |          ~~~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:93:27: warning: unused variable 'L' [-Wunused-variable]
   93 |  int addId = 0, lMax, id, L, R, mid, head;
      |                           ^
sortbooks.cpp:93:30: warning: unused variable 'R' [-Wunused-variable]
   93 |  int addId = 0, lMax, id, L, R, mid, head;
      |                              ^
sortbooks.cpp:93:33: warning: unused variable 'mid' [-Wunused-variable]
   93 |  int addId = 0, lMax, id, L, R, mid, head;
      |                                 ^~~
sortbooks.cpp:93:38: warning: unused variable 'head' [-Wunused-variable]
   93 |  int addId = 0, lMax, id, L, R, mid, head;
      |                                      ^~~~