oj.uz

Submission #960764

# Submission time Handle Problem Language Result Execution time Memory
960764 2024-04-11T03:07:01 Z Trisanu_Das Event Hopping (BOI22_events) C++17
40 / 100
 1500 ms 15016 KB 
#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" ;
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 78 ms 14500 KB Output is correct
3 Correct 529 ms 14956 KB Output is correct
4 Execution timed out 1528 ms 14872 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6760 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 2 ms 6744 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6760 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 2 ms 6744 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 1 ms 6748 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct
13 Correct 2 ms 6748 KB Output is correct
14 Correct 3 ms 6748 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 3 ms 6744 KB Output is correct
17 Correct 3 ms 6748 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 38 ms 9504 KB Output is correct
20 Correct 36 ms 9552 KB Output is correct
21 Correct 145 ms 10152 KB Output is correct
22 Correct 158 ms 10068 KB Output is correct
23 Correct 168 ms 9924 KB Output is correct
24 Correct 135 ms 9920 KB Output is correct
25 Correct 39 ms 9240 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6760 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 2 ms 6744 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 1 ms 7000 KB Output is correct
12 Correct 2 ms 6852 KB Output is correct
13 Correct 2 ms 6748 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 3 ms 6800 KB Output is correct
16 Correct 2 ms 6748 KB Output is correct
17 Correct 2 ms 6744 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 74 ms 12008 KB Output is correct
20 Correct 119 ms 11308 KB Output is correct
21 Correct 140 ms 11964 KB Output is correct
22 Correct 123 ms 12148 KB Output is correct
23 Correct 127 ms 12148 KB Output is correct
24 Correct 77 ms 11972 KB Output is correct
25 Correct 28 ms 11460 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 14532 KB Output is correct
2 Correct 535 ms 15016 KB Output is correct
3 Execution timed out 1528 ms 14752 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 78 ms 14500 KB Output is correct
3 Correct 529 ms 14956 KB Output is correct
4 Execution timed out 1528 ms 14872 KB Time limit exceeded
5 Halted 0 ms 0 KB -