oj.uz

답안 #601109

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
601109 2022-07-21T11:25:34 Z CSQ31 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 4848 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];
typedef pair<int,int> pii;
#define fi first
#define se second
pii T[8*MAXN];
pii mn[2*MAXN];
void build(int v,int l,int r){
	if(l==r){
		T[v] = mn[l];
		return;
	}
	int tm = (l+r)/2;
	build(2*v,l,tm);
	build(2*v+1,tm+1,r);
	T[v] = min(T[2*v],T[2*v+1]);
	
}
pii query(int v,int l,int r,int tl,int tr){
	if(l>r)return {1e9,-1};
	if(l==tl && r==tr)return T[v];
	int tm = (tl+tr)/2;
	return min(query(2*v,l,min(r,tm),tl,tm),
	           query(2*v+1,max(l,tm+1),r,tm+1,tr));
}
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=1;i<=m;i++)mn[i] = {i,-1};
	for(int i=0;i<n;i++)mn[e[i]] = min(mn[e[i]],{s[i],i});
	build(1,1,m);
	for(int i=0;i<n;i++){
		p[0][i] = i;
		for(int j=0;j<n;j++){
			pii res = query(1,s[i],e[i],1,m);
			if(res.se != -1)p[0][i] = res.se;	
		}
	}
	for(int i=1;i<=18;i++){
		for(int j=0;j<n;j++){
			p[i][j] = p[i-1][p[i-1][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;
		}
		if(s[r] <= e[l]){
			cout<<1<<'\n';
			continue;
		}
		int ans = 1; //one for actually arrivinf at l
		/*
		while(s[r] > e[l]){
			if(p[0][r] == r){
				ans = -1;
				break;
			}
			ans++;
			r = p[0][r];
		}*/
		for(int i=18;i>=0;i--){
			int v = p[i][r];
			if(s[v] > e[l]){
				r = v;
				ans+=(1<<i);
			}
		}
		ans++;
		if(r == p[0][r])ans=-1;	
		if(ans==-1)cout<<"impossible"<<'\n';
		else cout<<ans<<'\n';
	}
	
	
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 1570 ms 4816 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 68 ms 504 KB Output is correct
4 Correct 63 ms 508 KB Output is correct
5 Correct 60 ms 504 KB Output is correct
6 Correct 76 ms 508 KB Output is correct
7 Correct 107 ms 532 KB Output is correct
8 Correct 124 ms 536 KB Output is correct
9 Correct 4 ms 468 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 68 ms 504 KB Output is correct
4 Correct 63 ms 508 KB Output is correct
5 Correct 60 ms 504 KB Output is correct
6 Correct 76 ms 508 KB Output is correct
7 Correct 107 ms 532 KB Output is correct
8 Correct 124 ms 536 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 61 ms 512 KB Output is correct
13 Correct 61 ms 512 KB Output is correct
14 Correct 66 ms 508 KB Output is correct
15 Correct 72 ms 504 KB Output is correct
16 Correct 117 ms 532 KB Output is correct
17 Correct 123 ms 524 KB Output is correct
18 Correct 4 ms 468 KB Output is correct
19 Execution timed out 1584 ms 656 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 68 ms 504 KB Output is correct
4 Correct 63 ms 508 KB Output is correct
5 Correct 60 ms 504 KB Output is correct
6 Correct 76 ms 508 KB Output is correct
7 Correct 107 ms 532 KB Output is correct
8 Correct 124 ms 536 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 64 ms 504 KB Output is correct
13 Correct 77 ms 516 KB Output is correct
14 Correct 64 ms 588 KB Output is correct
15 Correct 73 ms 504 KB Output is correct
16 Correct 117 ms 532 KB Output is correct
17 Correct 147 ms 528 KB Output is correct
18 Correct 5 ms 468 KB Output is correct
19 Execution timed out 1573 ms 4760 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 1570 ms 4816 KB Time limit exceeded
3 Halted 0 ms 0 KB -