답안 #600994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
600994	2022-07-21T09:52:16 Z	CSQ31	Event Hopping (BOI22_events)	C++17	10 / 100	1500 ms	4104 KB

events

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1555 ms	2860 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 30.0

#	결과	실행 시간	메모리	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	-