Submission #1192933

#TimeUsernameProblemLanguageResultExecution timeMemory
1192933ildar1Comparing Plants (IOI20_plants)C++20
Compilation error
0 ms0 KiB
#include <iostream> #include <vector> #include <cassert> #include <stack> #define MAXN 200001 using namespace std; int ans[MAXN]; //ans[x] = rank of h[x] int myr[MAXN]; int next_bigger[MAXN]; //next_bigger[x] = index between x+1 and x+k-1 so that h[bigger[x]] int prev_bigger[MAXN]; //prev_bigger[x] = index between x-k+1 and x-1 so that h[prev_bigger[x]] is smallest term bigger than it else -1 stack<int> s; int n; int h; bool comparePairs(const pair<int,int> &p1, const pair<int,int> &p2) { if (p1.first < p2.first) return true; if (p1.first > p2.first) return false; if (p1.first==p2.first) { return p1.second >= p2.second; } } struct Seg{ pair<int,int> tree[2*MAXN]; int lazy[MAXN]; void make() { for (int i=0; i<n; i++) { tree[i+n].first = myr[i]; tree[i+n].second = i; } for (int i=n-1; i>0; i--) { tree[i] = min(tree[i<<1], tree[i<<1|1], comparePairs); /* tree[i] = min(tree[i<<1], tree[i<<1|1]); if (tree[i<<1].first==tree[i<<1|1].first) { tree[i].second = max(tree[i<<1|1].second, tree[i<<1].second); } */ } } void apply(int p, int val) { tree[p].first += val; if (p<n) lazy[p] += val; } void build(int p) { while (p>1) { p>>=1; pair<int,int> tmp1 = tree[p<<1]; tmp1.first += lazy[p]; pair<int, int> tmp2 = tree[p<<1|1]; tmp2.first += lazy[p]; tree[p].first = min(tmp1, tmp2, comparePairs) + lazy[p]; /* int x = tree[p<<1].first; int y = tree[p<<1|1].first; if (x<=y) { tree[p].first = x + lazy[p]; tree[p].second = (x<y) ? tree[p<<1].second: max(tree[p<<1|1].second, tree[p<<1].second); } else { tree[p].first = y+ lazy[p]; tree[p].second = tree[p<<1|1].second; } */ } } void push(int p) { for (int i=h; i>0; i--) { int j = p>>i; if (lazy[j] != 0) { apply(j<<1, lazy[j]); apply(j<<1|1, lazy[j]); lazy[j] = 0; } } } void increm(int l, int r, int val) { l+=n; r+=n; int l0 = l; int r0 = r; for (; l<r; l>>=1, r>>=1) { if (l&1) apply(l++, val); if (r&1) apply(--r, val); } build(l0); build(r0-1); } pair<int, int> query(int l, int r) { l+=n; r+=n; push(l); push(r-1); pair<int,int> res = {2e9, -1}; for (; l<r; l>>=1, r>>=1) { if (l&1) res = min(res, tree[l++]); if (r&1) res = min(res, tree[--r]); /* if (l&1) { int tmp3 = res.first; int tmp2 = res.second; res = min(res, tree[l]); if (tmp3==tree[l].first) res.second = max(tmp2, tree[l].second); l++; } if (r&1) { int tmp3 = res.first; int tmp2 = res.second; r--; res = min(res, tree[r]); if (tmp3==tree[r].first) res.second = max(tmp2, tree[r].second); } */ } return res; } } seg; void init(int k, vector<int> r) { n = r.size(); h = 31 - __builtin_clz(n); for (int i=0; i<n; i++) myr[i] = r[i]; seg.make(); int ind=seg.query(0,n).second; s.push(ind); for (int m=0; m<n; m++) { while (true) { if (!s.empty()) { int tmp = s.top(); if (tmp>=k-1 && seg.query(tmp-k+1, tmp).first>0) { s.pop(); ind = tmp; break; } else if (tmp>= k-1) { s.push(seg.query(tmp-k+1,tmp).second); } else if (tmp<k-1 && seg.query(0, tmp).first>0 && seg.query(n-k+tmp+1,n).first>0) { s.pop(); ind = tmp; break; } else if (tmp<k-1 && seg.query(0,tmp).first>0) { s.push(seg.query(n-k+tmp+1,n).second); } else { s.push(seg.query(0,tmp).second); } } else { if (seg.query(0, ind).first==0) { s.push(seg.query(0, ind).second); } else { s.push(seg.query(0, n).second); } } } ans[ind] = n-m; if (ind >= k-1) { seg.increm(ind-k+1, ind, -1); } else { seg.increm(0, ind, -1); seg.increm(n-k+ind+1, n, -1); } seg.increm(ind, ind+1, n); } } int compare_plants(int x, int y) { if (ans[x] > ans[y]) { return 1; } else return -1; }

Compilation message (stderr)

plants.cpp: In member function 'void Seg::build(int)':
plants.cpp:62:71: error: no match for 'operator+' (operand types are 'const std::pair<int, int>' and 'int')
   62 |                         tree[p].first = min(tmp1, tmp2, comparePairs) + lazy[p];
      |                                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ^ ~~~~~~~
      |                                            |                                  |
      |                                            const std::pair<int, int>          int
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/bits/char_traits.h:39,
                 from /usr/include/c++/11/ios:40,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from plants.cpp:1:
/usr/include/c++/11/bits/stl_iterator.h:585:5: note: candidate: 'template<class _Iterator> constexpr std::reverse_iterator<_IteratorL> std::operator+(typename std::reverse_iterator<_IteratorL>::difference_type, const std::reverse_iterator<_IteratorL>&)'
  585 |     operator+(typename reverse_iterator<_Iterator>::difference_type __n,
      |     ^~~~~~~~
/usr/include/c++/11/bits/stl_iterator.h:585:5: note:   template argument deduction/substitution failed:
plants.cpp:62:79: note:   mismatched types 'const std::reverse_iterator<_IteratorL>' and 'int'
   62 |                         tree[p].first = min(tmp1, tmp2, comparePairs) + lazy[p];
      |                                                                               ^
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/bits/char_traits.h:39,
                 from /usr/include/c++/11/ios:40,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from plants.cpp:1:
/usr/include/c++/11/bits/stl_iterator.h:1700:5: note: candidate: 'template<class _Iterator> constexpr std::move_iterator<_IteratorL> std::operator+(typename std::move_iterator<_IteratorL>::difference_type, const std::move_iterator<_IteratorL>&)'
 1700 |     operator+(typename move_iterator<_Iterator>::difference_type __n,
      |     ^~~~~~~~
/usr/include/c++/11/bits/stl_iterator.h:1700:5: note:   template argument deduction/substitution failed:
plants.cpp:62:79: note:   mismatched types 'const std::move_iterator<_IteratorL>' and 'int'
   62 |                         tree[p].first = min(tmp1, tmp2, comparePairs) + lazy[p];
      |                                                                               ^
In file included from /usr/include/c++/11/string:55,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from plants.cpp:1:
/usr/include/c++/11/bits/basic_string.h:6095:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 6095 |     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/basic_string.h:6095:5: note:   template argument deduction/substitution failed:
plants.cpp:62:79: note:   'const std::pair<int, int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   62 |                         tree[p].first = min(tmp1, tmp2, comparePairs) + lazy[p];
      |                                                                               ^
In file included from /usr/include/c++/11/string:56,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from plants.cpp:1:
/usr/include/c++/11/bits/basic_string.tcc:1169:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 1169 |     operator+(const _CharT* __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/basic_string.tcc:1169:5: note:   template argument deduction/substitution failed:
plants.cpp:62:79: note:   mismatched types 'const _CharT*' and 'std::pair<int, int>'
   62 |                         tree[p].first = min(tmp1, tmp2, comparePairs) + lazy[p];
      |                                                                               ^
In file included from /usr/include/c++/11/string:56,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from plants.cpp:1:
/usr/include/c++/11/bits/basic_string.tcc:1189:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(_CharT, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 1189 |     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/11/bits/basic_string.tcc:1189:5: note:   template argument deduction/substitution failed:
plants.cpp:62:79: note:   mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
   62 |                         tree[p].first = min(tmp1, tmp2, comparePairs) + lazy[p];
      |                                                                               ^
In file included from /usr/include/c++/11/string:55,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from plants.cpp:1:
/usr/include/c++/11/bits/basic_string.h:6132:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const _CharT*)'
 6132 |     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/basic_string.h:6132:5: note:   template argument deduction/substitution failed:
plants.cpp:62:79: note:   'const std::pair<int, int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   62 |                         tree[p].first = min(tmp1, tmp2, comparePairs) + lazy[p];
      |                                                                               ^
In file included from /usr/include/c++/11/string:55,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from plants.cpp:1:
/usr/include/c++/11/bits/basic_string.h:6148:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, _CharT)'
 6148 |     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
      |     ^~~~~~~~
/usr/include/c++/11/bits/basic_string.h:6148:5: note:   template argument deduction/substitution failed:
plants.cpp:62:79: note:   'const std::pair<int, int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   62 |                         tree[p].first = min(tmp1, tmp2, comparePairs) + lazy[p];
      |                                                                               ^
In file included from /usr/include/c++/11/string:55,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from plants.cpp:1:
/usr/include/c++/11/bits/basic_string.h:6160:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 6160 |     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/basic_string.h:6160:5: note:   template argument deduction/substitution failed:
plants.cpp:62:79: note:   types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'const std::pair<int, int>' have incompatible cv-qualifiers
   62 |                         tree[p].first = min(tmp1, tmp2, comparePairs) + lazy[p];
      |                                                                               ^
In file included from /usr/include/c++/11/string:55,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from plants.cpp:1:
/usr/include/c++/11/bits/basic_string.h:6166:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
 6166 |     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/basic_string.h:6166:5: note:   template argument deduction/substitution failed:
plants.cpp:62:79: note:   'const std::pair<int, int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   62 |                         tree[p].first = min(tmp1, tmp2, comparePairs) + lazy[p];
      |                                                                               ^
In file included from /usr/include/c++/11/string:55,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from plants.cpp:1:
/usr/include/c++/11/bits/basic_string.h:6172:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
 6172 |     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/basic_string.h:6172:5: note:   template argument deduction/substitution failed:
plants.cpp:62:79: note:   types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'const std::pair<int, int>' have incompatible cv-qualifiers
   62 |                         tree[p].first = min(tmp1, tmp2, comparePairs) + lazy[p];
      |                                                                               ^
In file included from /usr/include/c++/11/string:55,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from plants.cpp:1:
/usr/include/c++/11/bits/basic_string.h:6194:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const _CharT*, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
 6194 |     operator+(const _CharT* __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/basic_string.h:6194:5: note:   template argument deduction/substitution failed:
plants.cpp:62:79: note:   mismatched types 'const _CharT*' and 'std::pair<int, int>'
   62 |                         tree[p].first = min(tmp1, tmp2, comparePairs) + lazy[p];
      |                                                                               ^
In file included from /usr/include/c++/11/string:55,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from plants.cpp:1:
/usr/include/c++/11/bits/basic_string.h:6200:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(_CharT, std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
 6200 |     operator+(_CharT __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/basic_string.h:6200:5: note:   template argument deduction/substitution failed:
plants.cpp:62:79: note:   mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
   62 |                         tree[p].first = min(tmp1, tmp2, comparePairs) + lazy[p];
      |                                                                               ^
In file included from /usr/include/c++/11/string:55,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from plants.cpp:1:
/usr/include/c++/11/bits/basic_string.h:6206:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, const _CharT*)'
 6206 |     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/basic_string.h:6206:5: note:   template argument deduction/substitution failed:
plants.cpp:62:79: note:   types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'const std::pair<int, int>' have incompatible cv-qualifiers
   62 |                         tree[p].first = min(tmp1, tmp2, comparePairs) + lazy[p];
      |                                                                               ^
In file included from /usr/include/c++/11/string:55,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/ostream:38,
                 from /usr/include/c++/11/iostream:39,
                 from plants.cpp:1:
/usr/include/c++/11/bits/basic_string.h:6212:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, _CharT)'
 6212 |     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/basic_string.h:6212:5: note:   template argument deduction/substitution failed:
plants.cpp:62:79: note:   types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'const std::pair<int, int>' have incompatible cv-qualifiers
   62 |                         tree[p].first = min(tmp1, tmp2, comparePairs) + lazy[p];
      |                                                                               ^
plants.cpp: In function 'bool comparePairs(const std::pair<int, int>&, const std::pair<int, int>&)':
plants.cpp:28:1: warning: control reaches end of non-void function [-Wreturn-type]
   28 | }
      | ^