oj.uz

Submission #898286

# Submission time Handle Problem Language Result Execution time Memory
898286 2024-01-04T12:37:18 Z Litusiano Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
Compilation error
 0 ms 0 KB 
#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

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)); }
      |                ~~~~~~~^~~~~~~~~~~~~~