oj.uz

Submission #601111

# Submission time Handle Problem Language Result Execution time Memory
601111 2022-07-21T11:26:36 Z CSQ31 Event Hopping (BOI22_events) C++17
25 / 100
 1500 ms 4880 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++){
			if(s[i] <= e[j] && e[j] <= e[i]){
				if(s[j] < s[p[0][i]])p[0][i] = j;
			}	
		}
		/*
		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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 1596 ms 4864 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 560 KB Output is correct
8 Correct 3 ms 468 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 560 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 2 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 3 ms 468 KB Output is correct
13 Correct 4 ms 468 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 4 ms 468 KB Output is correct
16 Correct 5 ms 468 KB Output is correct
17 Correct 4 ms 548 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 128 ms 1556 KB Output is correct
20 Correct 98 ms 1552 KB Output is correct
21 Correct 98 ms 1796 KB Output is correct
22 Correct 108 ms 1808 KB Output is correct
23 Correct 123 ms 1868 KB Output is correct
24 Correct 97 ms 1900 KB Output is correct
25 Correct 100 ms 1556 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 560 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 4 ms 468 KB Output is correct
13 Correct 3 ms 468 KB Output is correct
14 Correct 3 ms 524 KB Output is correct
15 Correct 4 ms 524 KB Output is correct
16 Correct 5 ms 468 KB Output is correct
17 Correct 3 ms 548 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Execution timed out 1590 ms 4832 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 1586 ms 4880 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 340 KB Output is correct
2 Execution timed out 1596 ms 4864 KB Time limit exceeded
3 Halted 0 ms 0 KB -