Submission #544814

#	Time	Username	Problem	Language	Result	Execution time	Memory
544814		blue	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	654 ms	79168 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;

const int lg = 17;
const int Z = (1<<lg);

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

	int N, K;
	cin >> N >> K;

	int M;
	cin >> M;

	vi re(Z<<1, 1), le(Z<<1, N);

	for(int i = 1; i <= N; i++) re[i+Z] = le[i+Z] = i;

	// cerr << "A\n";

	for(int i = 1; i <= M; i++)
	{
		int A, B;
		cin >> A >> B;

		if(A < B)
		{
			int L = A + Z, R = min(A+K-1,B) + Z + 1;

			// cerr << '\n';
			// cerr << L-Z << ' ' << R-Z-1 << " -> " << B << '\n';

			while(L < R)
			{
				if(L & 1)
				{
					re[L] = max(re[L], B);
					L++;
				}

				if(R & 1)
				{
					R--;
					re[R] = max(re[R], B);
				}

				L >>= 1;
				R >>= 1;
			}
		}
		else
		{
			int L = max(A-K+1, B) + Z, R = A + Z + 1;

			// cerr << L-Z << ' ' << R-Z-1 << " <- " << B << '\n';

			while(L < R)
			{
				if(L & 1)
				{
					le[L] = min(le[L], B);
					L++;
				}

				if(R & 1)
				{
					R--;
					le[R] = min(le[R], B);
				}

				L >>= 1;
				R >>= 1;
			}
		}
	}

	// cerr << "B\n";

	vvi jmpL(1+N, vi(1+lg, N)), jmpR(1+N, vi(1+lg, 1));

	vvi Ltree(Z<<1, vi(1+lg, N)), Rtree(Z<<1, vi(1+lg, 1));

	for(int i = 1; i <= N; i++)
	{
		for(int j = i+Z; j >= 1; j >>= 1)
		{
			jmpL[i][0] = min(jmpL[i][0], le[j]);
			jmpR[i][0] = max(jmpR[i][0], re[j]);
		}

		Ltree[Z+i][0] = jmpL[i][0];
		Rtree[Z+i][0] = jmpR[i][0];
	}

	for(int z = Z-1; z >= 1; z--)
	{
		Ltree[z][0] = min(Ltree[2*z][0], Ltree[2*z+1][0]);
		Rtree[z][0] = max(Rtree[2*z][0], Rtree[2*z+1][0]);
	}

	// cerr << "C\n";


	// for(int i = 1; i <= N; i++) cerr << i << ' ' << 0 << " : " << jmpL[i][0] << ' ' << jmpR[i][0] << '\n';



	for(int e = 1; e <= lg; e++)
	{
		for(int i = 1; i <= N; i++)
		{
			int L = jmpL[i][e-1] + Z;
			int R = jmpR[i][e-1] + Z + 1;

			// for(int h = jmpL[i][e-1]; h <= jmpR[i][e-1]; h++)
			// {
			// 	jmpL[i][e] = min(jmpL[i][e], jmpL[h][e-1]);
			// 	jmpR[i][e] = max(jmpR[i][e], jmpR[h][e-1]);
			// }

			// cerr << i << ' ' << e << " : " << jmpL[i][e] << ' ' << jmpR[i][e] << '\n';


			while(L < R)
			{
				// cerr << L << ' ' << R << "\n";
				if(L & 1)
				{
					jmpL[i][e] = min(jmpL[i][e], Ltree[L][e-1]);
					jmpR[i][e] = max(jmpR[i][e], Rtree[L][e-1]);
					L++;
				}

				if(R & 1)
				{
					R--;
					jmpL[i][e] = min(jmpL[i][e], Ltree[R][e-1]);
					jmpR[i][e] = max(jmpR[i][e], Rtree[R][e-1]);
				}

				L >>= 1;
				R >>= 1;
			}

			Ltree[Z+i][e] = jmpL[i][e];
			Rtree[Z+i][e] = jmpR[i][e];
		}

		for(int z = Z-1; z >= 1; z--)
		{
			Ltree[z][e] = min(Ltree[2*z][e], Ltree[2*z+1][e]);
			Rtree[z][e] = max(Rtree[2*z][e], Rtree[2*z+1][e]);
		}
	}

	// cerr << "D\n";


	// for(int i = 1; i <= N; i++) cerr << i << " : " << jmpL[i][0] << ' ' << jmpR[i][0] << " - " << jmpL[i][lg] << ' ' << jmpR[i][lg] << '\n';





	int Q;
	cin >> Q;

	for(int q = 1; q <= Q; q++)
	{
		int S, T;
		cin >> S >> T;

		if(!(jmpL[S][lg] <= T && T <= jmpR[S][lg]))
		{
			cout << "-1\n";
			continue;
		}

		int ans = 1;

		int SL = S, SR = S;

		for(int e = lg; e >= 0; e--)
		{
			int NL = SL, NR = SR;

			int L = SL + Z;
			int R = SR + Z + 1;
			while(L < R)
			{
				if(L & 1)
				{
					NL = min(NL, Ltree[L][e]);
					NR = max(NR, Rtree[L][e]);
					L++;
				}

				if(R & 1)
				{
					R--;
					NL = min(NL, Ltree[R][e]);
					NR = max(NR, Rtree[R][e]);
				}

				L >>= 1;
				R >>= 1;
			}

			// cerr << SL << ' ' << SR << "\n";
			// cerr << "e = " << e << " : " << NL << ' ' << NR << '\n';

			if(NL <= T && T <= NR) continue;

			// cerr << "executed\n";


			ans += (1<<e);

			SL = NL, SR = NR;
		}


		cout << ans << '\n';
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13