Submission #960763

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
960763	2024-04-11T03:06:39 Z	Trisanu_Das	Event Hopping (BOI22_events)	C++17	Compilation error	0 ms	0 KB

events

#include <bits/stdc++.h>
using namespace std ;
const int inf = 1e9 ;
const int MAX = 2e5 + 10 ;
 
int L[MAX], R[MAX], n, q, dp[MAX], ans[MAX];
vector<array<int , 3> > v;
vector<pair<int, int> > queries[MAX] ;
 
void compress() {
	vector<int> v ;
	for(int i = 1; i <= n; i++) v.push_back(L[i]) , v.push_back(R[i]) ;
	sort(v.begin(), v.end()) ;
	v.erase(unique(v.begin(), v.end()), v.end()) ;
	for(int i = 1 ; i <= n ; i++) {
		L[i] = lower_bound(v.begin(), v.end(), L[i]) - v.begin() ;
		R[i] = lower_bound(v.begin(), v.end(), R[i]) - v.begin() ;
		L[i]++ , R[i]++ ;
	}
}
 
bool cmp(array<int , 3>&a , array<int , 3>&b) {
	if(a[1] != b[1]) return (a[1] < b[1]) ;
	else return (a[0] < b[0]) ;
}
 
void solve(int st) {
	if(!queries[st].size()) return;
	for(int i = 1 ; i <= n ; i++) dp[i] = inf;
	dp[st] = 0;
	stack<int> s;
	s.push(st);
	for(auto &a : v){
		int l = a[0], r = a[1], idx = a[2] ;
		if(idx == st || R[s.top()] > r) continue;
		int last = -1 ;
		while(s.size() && R[s.top()] >= l) {
			last = s.top() ;
			s.pop() ;
		}
		if(last == -1) continue;
		s.push(last) , s.push(idx) ;
		dp[idx] = dp[last] + 1 ;
	}
	for(auto &p : queries[st]) ans[p.second] = dp[p.first];
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n >>q  ;
	for(int i = 1; i <= n; i++) cin >> L[i] >> R[i] ;
	for(int i = 1; i <= q; i++) {
		int x, y; cin >> x >> y ;
		queries[x].push_back(y, i) ;
	}
	compress() ;
	for(int i = 1; i <= n; i++) v.push_back({L[i] , R[i] , i}) ;
	sort(v.begin() , v.end() , cmp) ;
	for(int i = 1; i <= n; i++) solve(i) ;
	for(int i = 1; i <= q; i++) {
		if(ans[i] != inf) cout << ans[i] << '\n' ;
		else cout << "impossible\n" ;
	}
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:54:28: error: no matching function for call to 'std::vector<std::pair<int, int> >::push_back(int&, int&)'
   54 |   queries[x].push_back(y, i) ;
      |                            ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from events.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note:   candidate expects 1 argument, 2 provided