oj.uz

Submission #544814

# Submission time Handle Problem Language Result Execution time Memory
544814 2022-04-02T18:42:27 Z blue Railway Trip 2 (JOI22_ho_t4) C++17
100 / 100
 654 ms 79168 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 55884 KB Output is correct
2 Correct 124 ms 55800 KB Output is correct
3 Correct 117 ms 55672 KB Output is correct
4 Correct 121 ms 55900 KB Output is correct
5 Correct 119 ms 55780 KB Output is correct
6 Correct 119 ms 55792 KB Output is correct
7 Correct 122 ms 55700 KB Output is correct
8 Correct 113 ms 55756 KB Output is correct
9 Correct 118 ms 55800 KB Output is correct
10 Correct 116 ms 55648 KB Output is correct
11 Correct 112 ms 55720 KB Output is correct
12 Correct 111 ms 55916 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 55884 KB Output is correct
2 Correct 124 ms 55800 KB Output is correct
3 Correct 117 ms 55672 KB Output is correct
4 Correct 121 ms 55900 KB Output is correct
5 Correct 119 ms 55780 KB Output is correct
6 Correct 119 ms 55792 KB Output is correct
7 Correct 122 ms 55700 KB Output is correct
8 Correct 113 ms 55756 KB Output is correct
9 Correct 118 ms 55800 KB Output is correct
10 Correct 116 ms 55648 KB Output is correct
11 Correct 112 ms 55720 KB Output is correct
12 Correct 111 ms 55916 KB Output is correct
13 Correct 120 ms 56176 KB Output is correct
14 Correct 128 ms 56172 KB Output is correct
15 Correct 124 ms 56160 KB Output is correct
16 Correct 132 ms 56052 KB Output is correct
17 Correct 115 ms 56176 KB Output is correct
18 Correct 124 ms 56148 KB Output is correct
19 Correct 115 ms 56152 KB Output is correct
20 Correct 123 ms 56272 KB Output is correct
21 Correct 122 ms 56216 KB Output is correct
22 Correct 125 ms 56172 KB Output is correct
23 Correct 125 ms 56176 KB Output is correct
24 Correct 123 ms 56140 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 77028 KB Output is correct
2 Correct 379 ms 76880 KB Output is correct
3 Correct 456 ms 77112 KB Output is correct
4 Correct 397 ms 76940 KB Output is correct
5 Correct 353 ms 78396 KB Output is correct
6 Correct 375 ms 78456 KB Output is correct
7 Correct 395 ms 78188 KB Output is correct
8 Correct 346 ms 77024 KB Output is correct
9 Correct 372 ms 77244 KB Output is correct
10 Correct 320 ms 78292 KB Output is correct
11 Correct 330 ms 78396 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 77832 KB Output is correct
2 Correct 353 ms 79080 KB Output is correct
3 Correct 432 ms 77992 KB Output is correct
4 Correct 429 ms 78652 KB Output is correct
5 Correct 381 ms 78748 KB Output is correct
6 Correct 420 ms 78884 KB Output is correct
7 Correct 328 ms 79044 KB Output is correct
8 Correct 435 ms 79128 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 79020 KB Output is correct
2 Correct 464 ms 77996 KB Output is correct
3 Correct 501 ms 77508 KB Output is correct
4 Correct 454 ms 77092 KB Output is correct
5 Correct 331 ms 76852 KB Output is correct
6 Correct 346 ms 76704 KB Output is correct
7 Correct 341 ms 77868 KB Output is correct
8 Correct 113 ms 55764 KB Output is correct
9 Correct 119 ms 56140 KB Output is correct
10 Correct 360 ms 78524 KB Output is correct
11 Correct 361 ms 78900 KB Output is correct
12 Correct 360 ms 78836 KB Output is correct
13 Correct 351 ms 78920 KB Output is correct
14 Correct 112 ms 55692 KB Output is correct
15 Correct 121 ms 56260 KB Output is correct
16 Correct 329 ms 78344 KB Output is correct
17 Correct 472 ms 79148 KB Output is correct
18 Correct 429 ms 79052 KB Output is correct
19 Correct 422 ms 79128 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 55884 KB Output is correct
2 Correct 124 ms 55800 KB Output is correct
3 Correct 117 ms 55672 KB Output is correct
4 Correct 121 ms 55900 KB Output is correct
5 Correct 119 ms 55780 KB Output is correct
6 Correct 119 ms 55792 KB Output is correct
7 Correct 122 ms 55700 KB Output is correct
8 Correct 113 ms 55756 KB Output is correct
9 Correct 118 ms 55800 KB Output is correct
10 Correct 116 ms 55648 KB Output is correct
11 Correct 112 ms 55720 KB Output is correct
12 Correct 111 ms 55916 KB Output is correct
13 Correct 120 ms 56176 KB Output is correct
14 Correct 128 ms 56172 KB Output is correct
15 Correct 124 ms 56160 KB Output is correct
16 Correct 132 ms 56052 KB Output is correct
17 Correct 115 ms 56176 KB Output is correct
18 Correct 124 ms 56148 KB Output is correct
19 Correct 115 ms 56152 KB Output is correct
20 Correct 123 ms 56272 KB Output is correct
21 Correct 122 ms 56216 KB Output is correct
22 Correct 125 ms 56172 KB Output is correct
23 Correct 125 ms 56176 KB Output is correct
24 Correct 123 ms 56140 KB Output is correct
25 Correct 398 ms 77028 KB Output is correct
26 Correct 379 ms 76880 KB Output is correct
27 Correct 456 ms 77112 KB Output is correct
28 Correct 397 ms 76940 KB Output is correct
29 Correct 353 ms 78396 KB Output is correct
30 Correct 375 ms 78456 KB Output is correct
31 Correct 395 ms 78188 KB Output is correct
32 Correct 346 ms 77024 KB Output is correct
33 Correct 372 ms 77244 KB Output is correct
34 Correct 320 ms 78292 KB Output is correct
35 Correct 330 ms 78396 KB Output is correct
36 Correct 415 ms 77832 KB Output is correct
37 Correct 353 ms 79080 KB Output is correct
38 Correct 432 ms 77992 KB Output is correct
39 Correct 429 ms 78652 KB Output is correct
40 Correct 381 ms 78748 KB Output is correct
41 Correct 420 ms 78884 KB Output is correct
42 Correct 328 ms 79044 KB Output is correct
43 Correct 435 ms 79128 KB Output is correct
44 Correct 385 ms 79020 KB Output is correct
45 Correct 464 ms 77996 KB Output is correct
46 Correct 501 ms 77508 KB Output is correct
47 Correct 454 ms 77092 KB Output is correct
48 Correct 331 ms 76852 KB Output is correct
49 Correct 346 ms 76704 KB Output is correct
50 Correct 341 ms 77868 KB Output is correct
51 Correct 113 ms 55764 KB Output is correct
52 Correct 119 ms 56140 KB Output is correct
53 Correct 360 ms 78524 KB Output is correct
54 Correct 361 ms 78900 KB Output is correct
55 Correct 360 ms 78836 KB Output is correct
56 Correct 351 ms 78920 KB Output is correct
57 Correct 112 ms 55692 KB Output is correct
58 Correct 121 ms 56260 KB Output is correct
59 Correct 329 ms 78344 KB Output is correct
60 Correct 472 ms 79148 KB Output is correct
61 Correct 429 ms 79052 KB Output is correct
62 Correct 422 ms 79128 KB Output is correct
63 Correct 465 ms 77728 KB Output is correct
64 Correct 654 ms 77864 KB Output is correct
65 Correct 492 ms 77712 KB Output is correct
66 Correct 391 ms 79092 KB Output is correct
67 Correct 533 ms 79140 KB Output is correct
68 Correct 362 ms 78784 KB Output is correct
69 Correct 402 ms 78928 KB Output is correct
70 Correct 352 ms 79020 KB Output is correct
71 Correct 461 ms 79168 KB Output is correct