Submission #201863

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
201863	2020-02-12T10:25:44 Z	theStaticMind	Two Antennas (JOI19_antennas)	C++14	Compilation error	0 ms	0 KB

antennas

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 2e9
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;

vector<int> segn, segx;
int S;
int get(int a, int b, bool mx){
      return (mx ? max(a, b) : min(a, b));
}
void build(vector<int>& seg, bool mx){
      S = (1ll << (int)ceil(log2(seg.size())));
      int l = S - seg.size();
      for(int i = 0; i < l; i++)seg.pb(mx?0:INF);
      reverse(all(seg));
      for(int i = 1; i < seg.size(); i += 2) seg.pb(get(seg[i - 1], seg[i], mx));
      seg.pb('a' + 't' + 'a' + 'k' + 'a' + 'n');
      reverse(all(seg));
}

int query(vector<int>& seg, int j, int a, int b, int x, int y, bool mx){
      if(y < a || b < x) return(mx ? 0 : INF);
      if(a <= x && y <= b) return seg[j];
      return  get(query(seg, j * 2, a, b, x, (x + y) / 2, mx), query(seg, j * 2 + 1, a ,b, (x + y) / 2 + 1, y, mx), mx);
}
void update(vector<int>& seg, int j, int v,bool mx){
      seg[j] = v;
      j /= 2;
      while(j > 0){
            seg[j] = get(seg[j * 2], seg[j * 2 + 1], mx);
            j /= 2;
      }
}
int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
   //   freopen("q.gir","r",stdin);
   //   freopen("q.cik","w",stdout);
      int n;
      cin >> n;
      vector<int> H(n + 1);
      vector<int> A(n + 1);
      vector<int> B(n+ 1);
      vector<int> sweep[2 * n + 5];
      unordered_set<int> curr;
      for(int i = 1; i <= n; i++){
            cin >> H[i] >> A[i] >> B[i];
            sweep[i + A[i]].pb(i);
            sweep[i + B[i]].pb(-i);
      }

      segn = vector<int>(n + 1, INF);
      segx = vector<int>(n + 1, 0);
      build(segx, true);
      build(segn, false);

      int q;
      cin >> q;
      vector<int> ans(q + 2, -1);
      vector<int> qq(q + 2);
      vector<int> Q[n + 2];
      for(int i = 1; i <= q; i++){
            int l, r;
            cin >> l >> r;
            Q[l].pb(i);
            Q[r + 1].pb(-i);
            qq[i] = l;
      }
      for(int i = 1; i <= n; i++){
            for(int j = 0; j < sweep[i].size(); j++){
                  int id = sweep[i][j];
                  if(id > 0){
                        update(segx, segx.size() - S + id, H[id], true);
                        update(segn, segn.size() - S + id, H[id], false);
                  }
            }
            for(int j = 0; j < Q[i].size(); j++){
                  int id = Q[i][j];
                  if(id > 0){
                        curr.insert(id);
                  }
                  else {
                        curr.erase(-id);
                  }
            }
            for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                  ans[*itr] = max(ans[*itr],
                      max(
                          query(segx, 1, max(i - B[i], qq[*itr]), i - A[i], 0, S - 1, true) - H[i] ,
                          H[i] - query(segn, 1, max(i - B[i], qq[*itr]), i - A[i], 0, S - 1, false)
                          )
                      );
            }

            for(int j = 0; j < sweep[i].size(); j++){
                  int id = sweep[i][j];
                  if(id < 0){
                        id = -id;
                        update(segx, segx.size() - S + id, 0, true);
                        update(segn, segn.size() - S + id, INF, false);
                  }
            }

      }
      for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

Compilation message

antennas.cpp: In function 'void build(std::vector<int>&, bool)':
antennas.cpp:22:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 1; i < seg.size(); i += 2) seg.pb(get(seg[i - 1], seg[i], mx));
                      ~~^~~~~~~~~~~~
antennas.cpp: In function 'int32_t main()':
antennas.cpp:76:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < sweep[i].size(); j++){
                            ~~^~~~~~~~~~~~~~~~~
antennas.cpp:83:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < Q[i].size(); j++){
                            ~~^~~~~~~~~~~~~
antennas.cpp:92:52: error: conversion from 'std::unordered_set<int>::iterator {aka std::__detail::_Node_iterator<int, true, false>}' to non-scalar type 'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' requested
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                          ~~~~~~~~~~^~
antennas.cpp:92:60: error: no match for 'operator!=' (operand types are 'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' and 'std::unordered_set<int>::iterator {aka std::__detail::_Node_iterator<int, true, false>}')
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                                        ~~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/7/map:60:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:81,
                 from antennas.cpp:1:
/usr/include/c++/7/bits/stl_tree.h:398:7: note: candidate: bool std::_Rb_tree_const_iterator<_Tp>::operator!=(const _Self&) const [with _Tp = int; std::_Rb_tree_const_iterator<_Tp>::_Self = std::_Rb_tree_const_iterator<int>]
       operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
       ^~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:398:7: note:   no known conversion for argument 1 from 'std::unordered_set<int>::iterator {aka std::__detail::_Node_iterator<int, true, false>}' to 'const _Self& {aka const std::_Rb_tree_const_iterator<int>&}'
In file included from /usr/include/c++/7/regex:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
                 from antennas.cpp:1:
/usr/include/c++/7/bits/regex.h:951:5: note: candidate: template<class _BiIter> bool std::__cxx11::operator!=(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)
     operator!=(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
     ^~~~~~~~
/usr/include/c++/7/bits/regex.h:951:5: note:   template argument deduction/substitution failed:
antennas.cpp:92:72: note:   'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                                                        ^
In file included from /usr/include/c++/7/regex:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
                 from antennas.cpp:1:
/usr/include/c++/7/bits/regex.h:1029:5: note: candidate: template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator!=(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)
     operator!=(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/regex.h:1029:5: note:   template argument deduction/substitution failed:
antennas.cpp:92:72: note:   'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                                                        ^
In file included from /usr/include/c++/7/regex:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
                 from antennas.cpp:1:
/usr/include/c++/7/bits/regex.h:1109:5: note: candidate: template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator!=(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)
     operator!=(const sub_match<_Bi_iter>& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/regex.h:1109:5: note:   template argument deduction/substitution failed:
antennas.cpp:92:72: note:   'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                                                        ^
In file included from /usr/include/c++/7/regex:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
                 from antennas.cpp:1:
/usr/include/c++/7/bits/regex.h:1186:5: note: candidate: template<class _Bi_iter> bool std::__cxx11::operator!=(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)
     operator!=(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/regex.h:1186:5: note:   template argument deduction/substitution failed:
antennas.cpp:92:72: note:   'std::unordered_set<int>::iterator {aka std::__detail::_Node_iterator<int, true, false>}' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                                                        ^
In file included from /usr/include/c++/7/regex:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
                 from antennas.cpp:1:
/usr/include/c++/7/bits/regex.h:1260:5: note: candidate: template<class _Bi_iter> bool std::__cxx11::operator!=(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)
     operator!=(const sub_match<_Bi_iter>& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/regex.h:1260:5: note:   template argument deduction/substitution failed:
antennas.cpp:92:72: note:   'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                                                        ^
In file included from /usr/include/c++/7/regex:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
                 from antennas.cpp:1:
/usr/include/c++/7/bits/regex.h:1337:5: note: candidate: template<class _Bi_iter> bool std::__cxx11::operator!=(const typename std::iterator_traits<_Iter>::value_type&, const std::__cxx11::sub_match<_BiIter>&)
     operator!=(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/regex.h:1337:5: note:   template argument deduction/substitution failed:
antennas.cpp:92:72: note:   'std::unordered_set<int>::iterator {aka std::__detail::_Node_iterator<int, true, false>}' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                                                        ^
In file included from /usr/include/c++/7/regex:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
                 from antennas.cpp:1:
/usr/include/c++/7/bits/regex.h:1417:5: note: candidate: template<class _Bi_iter> bool std::__cxx11::operator!=(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)
     operator!=(const sub_match<_Bi_iter>& __lhs,
     ^~~~~~~~
/usr/include/c++/7/bits/regex.h:1417:5: note:   template argument deduction/substitution failed:
antennas.cpp:92:72: note:   'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                                                        ^
In file included from /usr/include/c++/7/regex:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:110,
                 from antennas.cpp:1:
/usr/include/c++/7/bits/regex.h:1944:5: note: candidate: template<class _Bi_iter, class _Alloc> bool std::__cxx11::operator!=(const std::__cxx11::match_results<_BiIter, _Alloc>&, const std::__cxx11::match_results<_BiIter, _Alloc>&)
     operator!=(const match_results<_Bi_iter, _Alloc>& __m1,
     ^~~~~~~~
/usr/include/c++/7/bits/regex.h:1944:5: note:   template argument deduction/substitution failed:
antennas.cpp:92:72: note:   'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' is not derived from 'const std::__cxx11::match_results<_BiIter, _Alloc>'
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                                                        ^
In file included from /usr/include/c++/7/iosfwd:40:0,
                 from /usr/include/c++/7/ios:38,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from antennas.cpp:1:
/usr/include/c++/7/bits/postypes.h:221:5: note: candidate: template<class _StateT> bool std::operator!=(const std::fpos<_StateT>&, const std::fpos<_StateT>&)
     operator!=(const fpos<_StateT>& __lhs, const fpos<_StateT>& __rhs)
     ^~~~~~~~
/usr/include/c++/7/bits/postypes.h:221:5: note:   template argument deduction/substitution failed:
antennas.cpp:92:72: note:   'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' is not derived from 'const std::fpos<_StateT>'
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                                                        ^
In file included from /usr/include/c++/7/bits/stl_algobase.h:64:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from antennas.cpp:1:
/usr/include/c++/7/bits/stl_pair.h:456:5: note: candidate: template<class _T1, class _T2> constexpr bool std::operator!=(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)
     operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
     ^~~~~~~~
/usr/include/c++/7/bits/stl_pair.h:456:5: note:   template argument deduction/substitution failed:
antennas.cpp:92:72: note:   'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' is not derived from 'const std::pair<_T1, _T2>'
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                                                        ^
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from antennas.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:311:5: note: candidate: template<class _Iterator> bool std::operator!=(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
     operator!=(const reverse_iterator<_Iterator>& __x,
     ^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:311:5: note:   template argument deduction/substitution failed:
antennas.cpp:92:72: note:   'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' is not derived from 'const std::reverse_iterator<_Iterator>'
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                                                        ^
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from antennas.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:349:5: note: candidate: template<class _IteratorL, class _IteratorR> bool std::operator!=(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)
     operator!=(const reverse_iterator<_IteratorL>& __x,
     ^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:349:5: note:   template argument deduction/substitution failed:
antennas.cpp:92:72: note:   'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' is not derived from 'const std::reverse_iterator<_Iterator>'
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                                                        ^
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from antennas.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:1130:5: note: candidate: template<class _IteratorL, class _IteratorR> bool std::operator!=(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)
     operator!=(const move_iterator<_IteratorL>& __x,
     ^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:1130:5: note:   template argument deduction/substitution failed:
antennas.cpp:92:72: note:   'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' is not derived from 'const std::move_iterator<_IteratorL>'
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                                                        ^
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from antennas.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:1136:5: note: candidate: template<class _Iterator> bool std::operator!=(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)
     operator!=(const move_iterator<_Iterator>& __x,
     ^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:1136:5: note:   template argument deduction/substitution failed:
antennas.cpp:92:72: note:   'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' is not derived from 'const std::move_iterator<_IteratorL>'
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                                                        ^
In file included from /usr/include/c++/7/string:41:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from antennas.cpp:1:
/usr/include/c++/7/bits/allocator.h:158:5: note: candidate: template<class _T1, class _T2> bool std::operator!=(const std::allocator<_CharT>&, const std::allocator<_T2>&)
     operator!=(const allocator<_T1>&, const allocator<_T2>&)
     ^~~~~~~~
/usr/include/c++/7/bits/allocator.h:158:5: note:   template argument deduction/substitution failed:
antennas.cpp:92:72: note:   'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' is not derived from 'const std::allocator<_CharT>'
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                                                        ^
In file included from /usr/include/c++/7/string:41:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from antennas.cpp:1:
/usr/include/c++/7/bits/allocator.h:164:5: note: candidate: template<class _Tp> bool std::operator!=(const std::allocator<_CharT>&, const std::allocator<_CharT>&)
     operator!=(const allocator<_Tp>&, const allocator<_Tp>&)
     ^~~~~~~~
/usr/include/c++/7/bits/allocator.h:164:5: note:   template argument deduction/substitution failed:
antennas.cpp:92:72: note:   'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' is not derived from 'const std::allocator<_CharT>'
             for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                                                                        ^
In file included from /usr/include/c++/7/string:52:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /