Submission #857139

#	Time	Username	Problem	Language	Result	Execution time	Memory
857139		hail	Event Hopping (BOI22_events)	C++17	100 / 100	109 ms	30488 KiB

events

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back
#define fi first
#define se second
#define ld long double
#define pi pair<int, int>

const int INF = (int)4e18;
const int MODa = 1e9 + 7;
const int MOD = 998244353;

const int MXN = 100005;
int n, q;
int l[MXN]{};
int r[MXN]{};

int bl[MXN][25]{};

int cs(int a, int b)
{
	if(r[a]==r[b]) return l[a]>l[b];
	return r[a]>r[b];
}

int seg[4*MXN]{};
vector<int> ss(0);
vector<int> sl(0);

void build(int sl, int sr, int p)
{
	if(sl==sr)
	{
		seg[p] = ss[sl];
		return;
	}

	int m = (sl+sr)/2;
	build(sl, m, 2*p);
	build(m+1, sr, 2*p + 1);
	if(l[seg[2*p]]<=l[seg[2*p + 1]]) seg[p] = seg[2*p];
	else seg[p] = seg[2*p + 1];
}

int query(int sl, int sr, int p, int ql, int qr)
{
	if(sl>qr || ql>sr) return 0;
	if(ql<=sl && sr<=qr) return seg[p];

	int m = (sl+sr)/2;
	int x = query(sl, m, 2*p, ql, qr);
	int y = query(m+1, sr, 2*p + 1, ql, qr);
	if(l[x]<=l[y]) return x;
	return y;
}

void solve()
{
	cin>>n>>q;

	l[0] = INF;

	for(int i=1; i<=n; i++)
	{
		cin>>l[i]>>r[i];
	}

	ss.resize(n+1);
	sl.resize(n+2);
	iota(ss.begin(), ss.end(), 0);

	sort(ss.begin()+1, ss.end(), cs);

	for(int i=1; i<=n; i++)
	{
		sl[i] = -r[ss[i]];
	}

	build(1, n, 1);

	for(int i=1; i<=n; i++)
	{
		int j = ss[i];
		int lm = -l[j];
		int el = upper_bound(sl.begin()+1, sl.end(), lm) - sl.begin();
		bl[j][0] = query(1, n, 1, i, el-1);
	}

	for(int j=1; j<25; j++)
	{
		for(int i=1; i<=n; i++)
		{
			bl[i][j] = bl[bl[i][j-1]][j-1];
		}
	}

	for(int i=1; i<=q ;i++)
	{
		int s, e;
		cin>>s>>e;
		if(r[s]>r[e])
		{
			cout<<"impossible\n";
			continue;
		}
		int ans = 0;
		if(s==e)
		{
			cout<<0<<"\n";
			continue;
		}
		if(r[s]>=l[e])
		{
			cout<<1<<"\n";
			continue;
		}
		if(l[bl[e][24]]>r[s])
		{
			cout<<"impossible\n";
			continue;
		}
		int x = e;
		for(int j=24; j>=0; j--)
		{
			if(l[bl[x][j]]<=r[s]) continue;
			ans += (1<<j);
			x = bl[x][j];
		}
		cout<<ans+2<<"\n";
	}

}


signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t = 1;	
	//cin>>t;
	while(t--)
	{
		solve();
	}
	
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30