oj.uz

Submission #600994

# Submission time Handle Problem Language Result Execution time Memory
600994 2022-07-21T09:52:16 Z CSQ31 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 4104 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];
bool check(int x,int j){ //got edge i->j?
	return s[j] <= x && x <= e[j];
}
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();
		e[i] = lower_bound(all(crd),e[i]) - crd.begin();
	}
	int m = crd.size();

	//greedy : always jump to the rightmost guy with e < e[r]
	while(q--){
		int l,r;
		cin>>l>>r;
		l--;
		r--;
		int ans = 0;
		if(l==r){
			cout<<0<<'\n';
			continue;
		}
		int i = e[l];
		while(true){
			if(check(i,r)){
				ans++;
				break;
			}
			int k = i;
			for(int j=0;j<n;j++){
				if(check(i,j) && e[j] <= e[r])k = max(e[j],k);	
			}
			if(k==i){
				ans=-1;
				break;
			}
			ans++;
			i = k;
		}
		if(ans==-1)cout<<"impossible"<<'\n';
		else cout<<ans<<'\n';
	}
	
	
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:27:6: warning: unused variable 'm' [-Wunused-variable]
   27 |  int m = crd.size();
      |      ^

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 239 ms 348 KB Output is correct
4 Correct 35 ms 340 KB Output is correct
5 Correct 54 ms 356 KB Output is correct
6 Correct 2 ms 356 KB Output is correct
7 Correct 2 ms 372 KB Output is correct
8 Correct 2 ms 368 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 239 ms 348 KB Output is correct
4 Correct 35 ms 340 KB Output is correct
5 Correct 54 ms 356 KB Output is correct
6 Correct 2 ms 356 KB Output is correct
7 Correct 2 ms 372 KB Output is correct
8 Correct 2 ms 368 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 300 ms 352 KB Output is correct
13 Correct 32 ms 352 KB Output is correct
14 Correct 46 ms 356 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 2 ms 352 KB Output is correct
17 Correct 2 ms 352 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Execution timed out 1572 ms 568 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 239 ms 348 KB Output is correct
4 Correct 35 ms 340 KB Output is correct
5 Correct 54 ms 356 KB Output is correct
6 Correct 2 ms 356 KB Output is correct
7 Correct 2 ms 372 KB Output is correct
8 Correct 2 ms 368 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 238 ms 356 KB Output is correct
13 Correct 36 ms 348 KB Output is correct
14 Correct 41 ms 340 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Execution timed out 1557 ms 4104 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 1555 ms 2860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

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