oj.uz

Submission #601083

# Submission time Handle Problem Language Result Execution time Memory
601083 2022-07-21T10:59:25 Z CSQ31 Event Hopping (BOI22_events) C++17
25 / 100
 1500 ms 4040 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(),a.end()
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
const int MAXN = 1e5+1;
int s[MAXN],e[MAXN];
//fuck binlift how
//p(k,i) = min s if we jump backwards 2^k times
//p(k-1,i) = min of p(k-1),i<= x <= i ,p(k-1,x)
//yeesh but this n log^2n
//should pass maybe?
//1e5 * 18 * 18 = 3e7
int p[19][MAXN];
int main()
{
	owo
	int n,q;
	cin>>n>>q;
	vector<int>crd;
	for(int i=0;i<n;i++)cin>>s[i]>>e[i];
	for(int i=0;i<n;i++){
		crd.push_back(s[i]);
		crd.push_back(e[i]);
	}
	sort(all(crd));
	crd.resize(unique(all(crd)) - crd.begin());
	for(int i=0;i<n;i++){
		s[i] = lower_bound(all(crd),s[i]) - crd.begin()+1;
		e[i] = lower_bound(all(crd),e[i]) - crd.begin()+1;
	}
	//int m = crd.size();
	for(int i=0;i<n;i++){
		p[0][i] = i;
		for(int j=0;j<n;j++){
			if(s[i] <= e[j] && e[j] <= e[i]){
				if(s[j] < s[p[0][i]])p[0][i] = j;
			}	
		}
	}
	while(q--){
		int l,r;
		cin>>l>>r;
		l--;
		r--;
		if(l==r){
			cout<<0<<'\n';
			continue;
		}
		if(e[l] > e[r]){
			cout<<"impossible"<<'\n';
			continue;
		}
		int ans = 1;
		while(s[r] > e[l]){
			if(p[0][r] == r){
				ans = -1;
				break;
			}
			ans++;
			r = p[0][r];
		}
		if(ans==-1)cout<<"impossible"<<'\n';
		else cout<<ans<<'\n';
	}
	
	
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1579 ms 4040 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 3 ms 348 KB Output is correct
14 Correct 4 ms 340 KB Output is correct
15 Correct 4 ms 356 KB Output is correct
16 Correct 4 ms 340 KB Output is correct
17 Correct 3 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 575 ms 2076 KB Output is correct
20 Correct 1456 ms 2040 KB Output is correct
21 Correct 347 ms 2124 KB Output is correct
22 Correct 103 ms 2248 KB Output is correct
23 Correct 120 ms 2132 KB Output is correct
24 Correct 101 ms 2252 KB Output is correct
25 Correct 120 ms 1736 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 4 ms 356 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 4 ms 340 KB Output is correct
16 Correct 4 ms 340 KB Output is correct
17 Correct 3 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Execution timed out 1580 ms 3200 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1558 ms 3904 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1579 ms 4040 KB Time limit exceeded
3 Halted 0 ms 0 KB -