Submission #587362

#	Time	Username	Problem	Language	Result	Execution time	Memory
587362		blue	Event Hopping (BOI22_events)	C++17	100 / 100	746 ms	79096 KiB

events

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <queue>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
#define sz(x) int(x.size())

const int mx = 200'000;
const int lg = 18;

int mxv[1+mx][1+lg];
int bst[1+mx];

int jmp[1+mx][1+lg];

int rangemax(int l, int r)
{
	int z = bst[r-l+1];
	return max(mxv[l][z], mxv[r - (1 << z) + 1][z]);
}


int Z = 262144;
int stree[1+lg][(1<<19)];

int smax(int e, int l, int r)
{
	int ans = 0;
	l += Z;
	r += Z+1;

	while(l < r)
	{
		if(l & 1)
		{
			ans = max(ans, stree[e][l]);
			l++;
		}

		if(r & 1)
		{
			r--;
			ans = max(ans, stree[e][r]);
		}

		r >>= 1;
		l >>= 1;
	}

	return ans;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, Q;
	cin >> N >> Q;

	map<int, int> norm;

	vi S(1+N), E(1+N);
	for(int i = 1; i <= N; i++)
	{
		cin >> S[i] >> E[i];
		S[i] *= -1;
		E[i] *= -1;
		swap(S[i], E[i]);

		norm[S[i]] = 0;
		norm[E[i]] = 0;
	}

	int ct = 0;	
	for(auto& z : norm)
		z.second = ++ct;

	for(int i = 1; i <= N; i++)
	{
		S[i] = norm[S[i]];
		E[i] = norm[E[i]];
	}

	// cerr << "\n\n";
	// for(int i = 1; i <= N; i++)
	// 	cerr << S[i] << ' ' << E[i] << '\n';
	// cerr << "\n\n";


	for(int i = 0; i <= mx; i++)
		for(int j = 0; j <= lg; j++)
			mxv[i][j] = 0;

	for(int i = 1; i <= N; i++)
		mxv[S[i]][0] = max(mxv[S[i]][0], E[i]);

	for(int e = 1; e <= lg; e++)
	{
		for(int i = 0; i <= mx; i++)
		{
			mxv[i][e] = mxv[i][e-1];
			if(i + (1 << (e-1)) <= mx)
				mxv[i][e] = max(mxv[i][e], mxv[ i + (1 << (e-1)) ][e-1]);
		}
	}

	bst[1] = 0;
	for(int i = 1; i <= mx; i++)
	{
		bst[i] = bst[i-1];
		if((1 << (bst[i]+1)) == i)
			bst[i]++;
	}


	for(int i = 0; i <= mx; i++)
	{
		jmp[i][0] = max(i, mxv[i][0]);
	}

	for(int e = 0; e <= lg; e++)
	{

		if(e > 0)
		{
			for(int i = 0; i <= mx; i++)
			{
				// cerr << i << " : " << jmp[i][e-1];
				if(i > jmp[i][e-1])
				{
					// cerr << e-1 << '\n';
					// cerr << i << " : " << jmp[i][e-1] << '\n';
					while(1);
				}

				jmp[i][e] = 0;
				// for(int h = i; h <= jmp[i][e-1]; h++)
				// 	jmp[i][e] = max(jmp[i][e], jmp[h][e-1]);
				// jmp[i][e] = rangemax(i, jmp[i][e-1]);
				jmp[i][e] = smax(e-1, i, jmp[i][e-1]);
			}
		}
		
		for(int i = 0; i <= mx; i++)
			stree[e][Z+i] = jmp[i][e];

		for(int i = Z-1; i >= 0; i--)
			stree[e][i] = max(stree[e][2*i], stree[e][2*i + 1]);
	}
	// cerr << "check\n";





	for(int q = 1; q <= Q; q++)
	{
		int a, b;
		cin >> a >> b;
		swap(a, b);


		int lt = S[a], rt = E[a];

		if(a == b) 
		{
			cout << "0\n";
			continue;
		}
		else if(S[b] < S[a])
		{
			cout << "impossible\n";
			continue;
		}

		// int tot = 0;
		// for(int i = lt; i <= rt; i++)
		// 	tot = max(tot, jmp[i][lg]);

		int tot = smax(lg, lt, rt);

		if(tot < S[b])
		{
			cout << "impossible\n";
			continue;
		}

		int ans = 0;

		for(int e = lg; e >= 0; e--)
		{	

			// int nrt = 0;
			// for(int i = lt; i <= rt; i++)
			// 	nrt = max(nrt, jmp[i][e]);
			int nrt = smax(e, lt, rt);

			// cerr << "e = " << e << " : ";
			// cerr << lt << ' ' << rt << " -> " << lt << ' ' << nrt << " cmp " << S[b] << '\n';

			if(nrt < S[b])
			{
				rt = nrt;
				ans += (1<<e);
			}
			else if(nrt == S[b])
			{
				rt = nrt;
				ans += (1<<e);
				break;
			}
		}

		if(rt < S[b])
		{
			rt = S[b];
			ans++;
		}

		// cerr << "current lt rt = " << lt << ' ' << rt << '\n';
		ans++;
		
		cout << ans << '\n';
	}


}

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