Submission #898286

#TimeUsernameProblemLanguageResultExecution timeMemory
898286LitusianoHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
Compilation error
0 ms0 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include<bits/stdc++.h> using namespace std; #define ll int #define endl '\n' struct segTree{ vector<ll> v; vector<ll> upd; int size = 1; void init(int n){ while(size < n) size *= 2; v.assign(2 * size, 0); upd.assign(2 * size, 0); } void set(int l, int r, int x, int lx, int rx, ll u){ if(lx >= l && rx <= r){ v[x] += u * (rx - lx); upd[x] += u; return; } if(lx >= r || l >= rx) return; int m = (lx + rx) / 2; set(l, r, 2 * x + 1, lx, m, u); set(l, r, 2 * x + 2, m, rx, u); v[x] = v[2 * x + 1] + v[2 * x + 2] + upd[x] * (rx - lx); return; } void set(int l, int r, int u){ return set(l, r, 0, 0, size, u); } void build(vector<ll> &a, int x, int lx, int rx){ if (rx - lx == 1){ if (lx < (int)a.size()){ v[x] = a[lx]; } return; } int m = (lx + rx) / 2; build(a, 2 * x + 1, lx, m); build(a, 2 * x + 2, m, rx); v[x] = v[2 * x + 1] + v[2 * x + 2]; } void build(vector<ll>& a){ build(a, 0, 0, size); } pair<ll, int> sum(int l, int r, int x, int lx, int rx){ if(lx >= l && rx <= r) return {v[x], rx - lx}; else if(lx >= r || rx <= l) return {0, 0}; int m = (lx + rx) / 2; pair<ll, int> s1 = sum(l, r, 2 * x + 1, lx, m); pair<ll, int> s2 = sum(l, r, 2 * x + 2, m, rx); return {s1.first + s2.first + upd[x] * (s1.second + s2.second), (s1.second + s2.second)}; } ll sum(int l, int r){ pair<ll, int> p = sum(l, r, 0, 0, size); return p.first; } }; bool cmp(pair<pair<int,int, pair<int,int>>> a, pair<pair<int,int, pair<int,int>>> b){ return a.first.first > b.first.first; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n,q; cin>>n>>q; vector<int> v(n); for(int& i : v) cin>>i; vector<int> pre(n+1); vector<int> inv; for(int i = 1; i<n; i++){ pre[i+1] = pre[i] + (v[i] < v[i-1]); if(v[i] < v[i-1]) inv.push_back(i-1); } vector<tuple<int,int,int,int,int>> st; for(int _ = 0; _<q; _++){ int l,r,k; cin>>l>>r>>k; if(n > 100000){ if(pre[r] - pre[l] == 0) cout<<1<<endl; else cout<<0<<endl; } else{ l--; r--; int mx = 0; int idx = lower_bound(inv.begin(),inv.end(),l) - inv.begin(); // cerr<<"INV "; for(int x = idx; x < inv.size(); x++){ // cerr<<inv[x]<<" "; if(inv[x] >= r) break; int i = inv[x]; int l1 = max(0, k-v[i]+1); int r1 = v[inv[x]]-1; // cerr<<"HERE! "<<inv[x]<<" "<<r<<" "<<l1<<" "<<r1<<" "<<k<<" "<<v[i]<<endl; if(l1 > r1) continue; st.push_back({i,r,l1,r1,_}); // cerr<<i+1<<" "<<r<<endl; // cerr<<"QUERY: "<<i<<" "<< seg.query(i+1,r,v[i])<<endl; } // cerr<<endl; } } if(n > 100000) return 0; vector<vector<pair<pair<int,int>,pair<int,int>>>> a(n); // at time i for(auto x : st){ int l,r,l1,r1,k; tie(l,r,l1,r1,k) = x; a[l].push_back({{1,k},{l1,r1}}); a[r].push_back({{-1,k},{l1,r1}}); } for(int i = 0; i<n; i++){ a[i].push_back({{0,0},{i,i}}); } for(int i = 0; i<n; i++){ sort(a[i].begin(),a[i].end(),cmp); } segTree seg; seg.init(1001); unordered_multiset<int> act; unordered_set<int> ans; for(auto x : a){ for(auto y : x){ int tp = y.first.first; int k = y.first.second; int l = y.second.first; int r = y.second.second; if(tp == 1){ seg.set(l,r+1,1); act.insert(k); } else if(tp == 0){ if(seg.sum(l,l+1) == 0) continue; for(int i : act) ans.insert(i); } else{ seg.set(l,r+1,-1); act.erase(act.find(k)); } } } // cout<<"Q "<<q<<endl; for(int i = 0; i<q; i++){ if(ans.count(i)) cout<<"0"<<endl; else cout<<"1"<<endl; } }

Compilation message (stderr)

sortbooks.cpp:67:41: error: wrong number of template arguments (3, should be 2)
   67 | bool cmp(pair<pair<int,int, pair<int,int>>> a, pair<pair<int,int, pair<int,int>>> b){
      |                                         ^~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from sortbooks.cpp:3:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: provided for 'template<class _T1, class _T2> struct std::pair'
  211 |     struct pair
      |            ^~~~
sortbooks.cpp:67:43: error: wrong number of template arguments (1, should be 2)
   67 | bool cmp(pair<pair<int,int, pair<int,int>>> a, pair<pair<int,int, pair<int,int>>> b){
      |                                           ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from sortbooks.cpp:3:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: provided for 'template<class _T1, class _T2> struct std::pair'
  211 |     struct pair
      |            ^~~~
sortbooks.cpp:67:79: error: wrong number of template arguments (3, should be 2)
   67 | bool cmp(pair<pair<int,int, pair<int,int>>> a, pair<pair<int,int, pair<int,int>>> b){
      |                                                                               ^~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from sortbooks.cpp:3:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: provided for 'template<class _T1, class _T2> struct std::pair'
  211 |     struct pair
      |            ^~~~
sortbooks.cpp:67:81: error: wrong number of template arguments (1, should be 2)
   67 | bool cmp(pair<pair<int,int, pair<int,int>>> a, pair<pair<int,int, pair<int,int>>> b){
      |                                                                                 ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from sortbooks.cpp:3:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: provided for 'template<class _T1, class _T2> struct std::pair'
  211 |     struct pair
      |            ^~~~
sortbooks.cpp: In function 'bool cmp(int, int)':
sortbooks.cpp:68:11: error: request for member 'first' in 'a', which is of non-class type 'int'
   68 |  return a.first.first > b.first.first;
      |           ^~~~~
sortbooks.cpp:68:27: error: request for member 'first' in 'b', which is of non-class type 'int'
   68 |  return a.first.first > b.first.first;
      |                           ^~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:94:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int x = idx; x < inv.size(); x++){
      |                      ~~^~~~~~~~~~~~
sortbooks.cpp:91:9: warning: unused variable 'mx' [-Wunused-variable]
   91 |     int mx = 0;
      |         ^~
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from sortbooks.cpp:3:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Iterator2 = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Compare = bool (*)(int, int)]':
/usr/include/c++/10/bits/stl_algo.h:82:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1924:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1958:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Compare = bool (*)(int, int)]'
sortbooks.cpp:120:37:   required from here
/usr/include/c++/10/bits/predefined_ops.h:156:30: error: cannot convert 'std::pair<std::pair<int, int>, std::pair<int, int> >' to 'int' in argument passing
  156 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = std::pair<std::pair<int, int>, std::pair<int, int> >; _Iterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Compare = bool (*)(int, int)]':
/usr/include/c++/10/bits/stl_algo.h:1826:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<bool (*)(int, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1854:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1886:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1977:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Compare = bool (*)(int, int)]'
sortbooks.cpp:120:37:   required from here
/usr/include/c++/10/bits/predefined_ops.h:238:23: error: cannot convert 'std::pair<std::pair<int, int>, std::pair<int, int> >' to 'int' in argument passing
  238 |  { return bool(_M_comp(__val, *__it)); }
      |                ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Value = std::pair<std::pair<int, int>, std::pair<int, int> >; _Compare = bool (*)(int, int)]':
/usr/include/c++/10/bits/stl_heap.h:139:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Distance = long int; _Tp = std::pair<std::pair<int, int>, std::pair<int, int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_val<bool (*)(int, int)>]'
/usr/include/c++/10/bits/stl_heap.h:246:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Distance = long int; _Tp = std::pair<std::pair<int, int>, std::pair<int, int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
/usr/include/c++/10/bits/stl_heap.h:355:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1666:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1937:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1953:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, std::pair<int, int> >*, std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > > >; _Compare = bool (*)(int, int)]'
sortbooks.cpp:120:37:   required from here
/usr/include/c++/10/bits/predefined_ops.h:194:23: error: cannot convert 'std::pair<std::pair<int, int>, std::pair<int, int> >' to 'int' in argument passing
  194 |  { return bool(_M_comp(*__it, __val)); }
      |                ~~~~~~~^~~~~~~~~~~~~~