oj.uz

Submission #978226

# Submission time Handle Problem Language Result Execution time Memory
978226 2024-05-09T04:11:48 Z model_code Escape Route 2 (JOI24_escape2) C++17
100 / 100
 1462 ms 266940 KB 
#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include <vector>
using std::pair;
using std::vector;
#include <algorithm>
using std::sort;
using std::min;
using std::max;
#include <map>
using std::map;

#ifdef DEBUG
#include <chrono>
std::chrono::system_clock::time_point chrono_start, chrono_prev;
void setstart (void) {
	chrono_prev = chrono_start = std::chrono::system_clock::now();
}
double elapsed (int id = 0) {
	auto now = std::chrono::system_clock::now();
	double x = std::chrono::duration_cast<std::chrono::milliseconds>(now - chrono_start).count();
	double y = std::chrono::duration_cast<std::chrono::milliseconds>(now - chrono_prev ).count();
	cerr << "elapsed " << id << ":\t" << x << "\t" << y << endl;
	chrono_prev = now;
	return x;
}
#else
void setstart (void) {
	return;
}
double elapsed (int id = 0) {
	return 0;
}
#endif


typedef long long int ll;
typedef pair<ll, ll> P;
typedef pair<P, ll> T;

int n, q;
ll t;
vector<int> m;
vector<int> cum;
vector<vector<P> > a;
vector<vector<P> > idxls, idxrs;
vector<int> ql, qr;

// doubR[k][i][e] := (v, e_opt) which minimizes v where
// v := (leaving time of a[min(i+2^k, n-1)][e_opt]) - (leaving time of a[i][e])
// doubL[k][i][e] := (v, e_opt) which minimizes v where
// v := (arriing time of a[i][e]) - (arriving time of a[max(i-2^k, 1)][e_opt])
// vector<vector<P> > jmpL, jmpR;
const int BITS = 20;
vector<vector<P> > doubL[BITS], doubR[BITS];
map<P, ll> memo;
void doubinit () {
	
	doubR[0].resize(n+1);
	for (int i = 1; i <= n - 2; i++) {
		doubR[0][i].resize(m[i]);

		int jrx = m[i+1];

		// This init value is for midnight-passing
		int vr = idxrs[i+1][0].second; // a[i+1][*].second min
		ll v = t + a[i+1][vr].second;

		// a[i][*].second decreasing
		for (int jlx = m[i] - 1; jlx >= 0; jlx--) {
			int jl = idxrs[i][jlx].second;
			
			// a[i+1][*].first decreasing
			while (jrx > 0) {
				// cerr << jlx << " " << jrx << std::endl;
				int jr = idxls[i+1][jrx - 1].second;
				// cerr << jl << " " << jr << std::endl;

				ll x;
				if (a[i][jl].second <= a[i + 1][jr].first) {
					--jrx;
					x = a[i + 1][jr].second;
					if (v > x) {
						v = x;
						vr = jr;
					}
				} else {
					break;
				}
			}

			doubR[0][i][jl] = (P){v - a[i][jl].second, vr};
		}
	}
	doubR[0][n-1].resize(m[n-1]);
	for (int jl = 0; jl < m[n-1]; jl++) {
		doubR[0][n-1][jl] = (P){0LL, jl};
	}

	doubL[0].resize(n+1);
	for (int i = n - 1; i >= 2; i--) {
		doubL[0][i].resize(m[i]);

		int jrx = -1;

		// This init value is for midnight-passing
		int vr = idxls[i-1][m[i-1]-1].second; // a[i-1][*].first max
		ll v = -t + a[i-1][vr].first;

		// a[i][*].first increasing
		for (int jlx = 0; jlx < m[i]; jlx++) {
			int jl = idxls[i][jlx].second;
			
			// a[i-1][*].second increasing
			while (jrx < m[i-1] - 1) {
				int jr = idxrs[i-1][jrx + 1].second;

				ll x;
				if (a[i-1][jr].second <= a[i][jl].first) {
					++jrx;
					x = a[i-1][jr].first;
					if (v < x) {
						v = x;
						vr = jr;
					}
				} else {
					break;
				}
			}

			doubL[0][i][jl] = (P){a[i][jl].first - v, vr};
		}
	}
	doubL[0][1].resize(m[1]);
	for (int jl = 0; jl < m[1]; jl++) {
		doubL[0][1][jl] = (P){0LL, jl};
	}
	

	for (int b = 1; b < BITS; b++) {
		doubR[b].resize(n+1);
		for (int i = 1; i <= n - 1; i++) {
			doubR[b][i].resize(m[i]);
			for (int j = 0; j < m[i]; j++) {
				P pl = doubR[b-1][i][j];
				int im = min(i + (1 << (b-1)), n-1);
				P pr = doubR[b-1][im][pl.second];
				
				doubR[b][i][j] = (P){pl.first + pr.first, pr.second};
			}
		}
	}
	for (int b = 1; b < BITS; b++) {
		doubL[b].resize(n+1);
		for (int i = 1; i <= n - 1; i++) {
			doubL[b][i].resize(m[i]);
			for (int j = 0; j < m[i]; j++) {
				P pl = doubL[b-1][i][j];
				int im = max(i - (1 << (b-1)), 1);
				P pr = doubL[b-1][im][pl.second];
				
				doubL[b][i][j] = (P){pl.first + pr.first, pr.second};
			}
		}
	}
}
void solve () {

	elapsed(0);

	doubinit();

	elapsed(1);

	// cerr << "a" << std::endl;

	for (int i = 0; i < q; i++) {
		ll x;
		const P querypair = (P){ql[i], qr[i]};
		if (memo.find(querypair) != memo.end()) {
			x = memo[querypair];
		} else {
			x = n * t;
			if (m[ql[i]] < m[qr[i] - 1]) {
				// use doubR
					
				for (int jl = 0; jl < m[ql[i]]; jl++) {
					ll sum = (a[ql[i]][jl].second - a[ql[i]][jl].first);
					int ic = ql[i], jc = jl;
					int c = (qr[i] - 1) - ql[i];
					for (int k = BITS - 1; k >= 0; k--) {
						if (c & (1 << k)) {
							P p = doubR[k][ic][jc];

							sum += p.first;

							ic = min(ic + (1 << k), n-1);
							jc = p.second;
						}
					}

					x = min(x, sum);
				}
			} else {
				// use doubL

				for (int jl = 0; jl < m[qr[i] - 1]; jl++) {
					ll sum = (a[qr[i] - 1][jl].second - a[qr[i] - 1][jl].first);
					int ic = qr[i] - 1, jc = jl;
					int c = (qr[i] - 1) - ql[i];
					for (int k = BITS - 1; k >= 0; k--) {
						if (c & (1 << k)) {
							P p = doubL[k][ic][jc];

							sum += p.first;

							ic = max(ic - (1 << k), 1);
							jc = p.second;
						}
					}

					x = min(x, sum);
				}
			}

			memo[querypair] = x;
		}

		cout << x << "\n";
	}

	elapsed(2);
}

int main (void) {
	cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);

	setstart();

	cin >> n >> t;

	m.resize(n+1);
	a.resize(n+1);
	idxls.resize(n+1);
	idxrs.resize(n+1);
	for (int i = 1; i <= n - 1; i++) {
		cin >> m[i];

		a[i].resize(m[i]);
		for (int j = 0; j < m[i]; j++) {
			cin >> a[i][j].first >> a[i][j].second;
		}
		sort(a[i].begin(), a[i].end());
		
		idxls[i].resize(m[i]);
		for (int j = 0; j < m[i]; j++) {
			idxls[i][j] = (P){a[i][j].first, (ll)j};
		}
		sort(idxls[i].begin(), idxls[i].end());
		idxrs[i].resize(m[i]);
		for (int j = 0; j < m[i]; j++) {
			idxrs[i][j] = (P){a[i][j].second, (ll)j};
		}
		sort(idxrs[i].begin(), idxrs[i].end());
	}

	cin >> q;

	ql.resize(q);
	qr.resize(q);
	for (int i = 0; i < q; i++) {
		cin >> ql[i] >> qr[i];
	}


	solve();


	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 58 ms 6768 KB Output is correct
3 Correct 199 ms 23976 KB Output is correct
4 Correct 313 ms 31852 KB Output is correct
5 Correct 290 ms 25780 KB Output is correct
6 Correct 344 ms 31524 KB Output is correct
7 Correct 269 ms 31340 KB Output is correct
8 Correct 210 ms 23536 KB Output is correct
9 Correct 323 ms 31288 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 58 ms 6768 KB Output is correct
3 Correct 199 ms 23976 KB Output is correct
4 Correct 313 ms 31852 KB Output is correct
5 Correct 290 ms 25780 KB Output is correct
6 Correct 344 ms 31524 KB Output is correct
7 Correct 269 ms 31340 KB Output is correct
8 Correct 210 ms 23536 KB Output is correct
9 Correct 323 ms 31288 KB Output is correct
10 Correct 1 ms 356 KB Output is correct
11 Correct 208 ms 15504 KB Output is correct
12 Correct 171 ms 15400 KB Output is correct
13 Correct 174 ms 15196 KB Output is correct
14 Correct 182 ms 15188 KB Output is correct
15 Correct 258 ms 22148 KB Output is correct
16 Correct 67 ms 6880 KB Output is correct
17 Correct 244 ms 28228 KB Output is correct
18 Correct 251 ms 23052 KB Output is correct
19 Correct 284 ms 28656 KB Output is correct
20 Correct 230 ms 21784 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 58 ms 6768 KB Output is correct
3 Correct 199 ms 23976 KB Output is correct
4 Correct 313 ms 31852 KB Output is correct
5 Correct 290 ms 25780 KB Output is correct
6 Correct 344 ms 31524 KB Output is correct
7 Correct 269 ms 31340 KB Output is correct
8 Correct 210 ms 23536 KB Output is correct
9 Correct 323 ms 31288 KB Output is correct
10 Correct 749 ms 205892 KB Output is correct
11 Correct 1069 ms 263916 KB Output is correct
12 Correct 1119 ms 264140 KB Output is correct
13 Correct 798 ms 257928 KB Output is correct
14 Correct 928 ms 266940 KB Output is correct
15 Correct 939 ms 266940 KB Output is correct
16 Correct 682 ms 208064 KB Output is correct
17 Correct 1133 ms 261932 KB Output is correct
18 Correct 497 ms 223140 KB Output is correct
19 Correct 414 ms 222192 KB Output is correct
20 Correct 472 ms 220568 KB Output is correct
21 Correct 450 ms 222384 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 58 ms 6768 KB Output is correct
3 Correct 199 ms 23976 KB Output is correct
4 Correct 313 ms 31852 KB Output is correct
5 Correct 290 ms 25780 KB Output is correct
6 Correct 344 ms 31524 KB Output is correct
7 Correct 269 ms 31340 KB Output is correct
8 Correct 210 ms 23536 KB Output is correct
9 Correct 323 ms 31288 KB Output is correct
10 Correct 1 ms 356 KB Output is correct
11 Correct 208 ms 15504 KB Output is correct
12 Correct 171 ms 15400 KB Output is correct
13 Correct 174 ms 15196 KB Output is correct
14 Correct 182 ms 15188 KB Output is correct
15 Correct 258 ms 22148 KB Output is correct
16 Correct 67 ms 6880 KB Output is correct
17 Correct 244 ms 28228 KB Output is correct
18 Correct 251 ms 23052 KB Output is correct
19 Correct 284 ms 28656 KB Output is correct
20 Correct 230 ms 21784 KB Output is correct
21 Correct 749 ms 205892 KB Output is correct
22 Correct 1069 ms 263916 KB Output is correct
23 Correct 1119 ms 264140 KB Output is correct
24 Correct 798 ms 257928 KB Output is correct
25 Correct 928 ms 266940 KB Output is correct
26 Correct 939 ms 266940 KB Output is correct
27 Correct 682 ms 208064 KB Output is correct
28 Correct 1133 ms 261932 KB Output is correct
29 Correct 497 ms 223140 KB Output is correct
30 Correct 414 ms 222192 KB Output is correct
31 Correct 472 ms 220568 KB Output is correct
32 Correct 450 ms 222384 KB Output is correct
33 Correct 786 ms 131904 KB Output is correct
34 Correct 767 ms 130032 KB Output is correct
35 Correct 801 ms 124988 KB Output is correct
36 Correct 814 ms 124888 KB Output is correct
37 Correct 787 ms 141980 KB Output is correct
38 Correct 737 ms 163540 KB Output is correct
39 Correct 836 ms 206296 KB Output is correct
40 Correct 815 ms 109244 KB Output is correct
41 Correct 724 ms 159928 KB Output is correct
42 Correct 918 ms 210264 KB Output is correct
43 Correct 649 ms 147928 KB Output is correct
44 Correct 798 ms 154708 KB Output is correct
45 Correct 387 ms 172804 KB Output is correct
46 Correct 459 ms 118996 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 379 ms 68304 KB Output is correct
4 Correct 362 ms 68100 KB Output is correct
5 Correct 380 ms 68292 KB Output is correct
6 Correct 439 ms 68084 KB Output is correct
7 Correct 375 ms 68112 KB Output is correct
8 Correct 374 ms 68380 KB Output is correct
9 Correct 224 ms 68420 KB Output is correct
10 Correct 67 ms 64196 KB Output is correct
11 Correct 448 ms 223240 KB Output is correct
12 Correct 417 ms 172780 KB Output is correct
13 Correct 429 ms 121760 KB Output is correct
14 Correct 201 ms 101312 KB Output is correct
15 Correct 198 ms 100524 KB Output is correct
16 Correct 315 ms 103792 KB Output is correct
17 Correct 296 ms 102768 KB Output is correct
18 Correct 143 ms 70740 KB Output is correct
19 Correct 203 ms 67904 KB Output is correct
20 Correct 270 ms 176632 KB Output is correct
21 Correct 313 ms 178752 KB Output is correct
22 Correct 253 ms 121936 KB Output is correct
23 Correct 289 ms 123764 KB Output is correct
24 Correct 216 ms 124336 KB Output is correct
25 Correct 156 ms 121720 KB Output is correct
26 Correct 249 ms 123324 KB Output is correct
27 Correct 387 ms 222184 KB Output is correct
28 Correct 445 ms 223464 KB Output is correct
29 Correct 434 ms 223340 KB Output is correct
30 Correct 212 ms 80376 KB Output is correct
31 Correct 98 ms 65360 KB Output is correct
32 Correct 279 ms 74316 KB Output is correct
33 Correct 99 ms 66052 KB Output is correct
34 Correct 314 ms 69416 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 58 ms 6768 KB Output is correct
3 Correct 199 ms 23976 KB Output is correct
4 Correct 313 ms 31852 KB Output is correct
5 Correct 290 ms 25780 KB Output is correct
6 Correct 344 ms 31524 KB Output is correct
7 Correct 269 ms 31340 KB Output is correct
8 Correct 210 ms 23536 KB Output is correct
9 Correct 323 ms 31288 KB Output is correct
10 Correct 1 ms 356 KB Output is correct
11 Correct 208 ms 15504 KB Output is correct
12 Correct 171 ms 15400 KB Output is correct
13 Correct 174 ms 15196 KB Output is correct
14 Correct 182 ms 15188 KB Output is correct
15 Correct 258 ms 22148 KB Output is correct
16 Correct 67 ms 6880 KB Output is correct
17 Correct 244 ms 28228 KB Output is correct
18 Correct 251 ms 23052 KB Output is correct
19 Correct 284 ms 28656 KB Output is correct
20 Correct 230 ms 21784 KB Output is correct
21 Correct 749 ms 205892 KB Output is correct
22 Correct 1069 ms 263916 KB Output is correct
23 Correct 1119 ms 264140 KB Output is correct
24 Correct 798 ms 257928 KB Output is correct
25 Correct 928 ms 266940 KB Output is correct
26 Correct 939 ms 266940 KB Output is correct
27 Correct 682 ms 208064 KB Output is correct
28 Correct 1133 ms 261932 KB Output is correct
29 Correct 497 ms 223140 KB Output is correct
30 Correct 414 ms 222192 KB Output is correct
31 Correct 472 ms 220568 KB Output is correct
32 Correct 450 ms 222384 KB Output is correct
33 Correct 786 ms 131904 KB Output is correct
34 Correct 767 ms 130032 KB Output is correct
35 Correct 801 ms 124988 KB Output is correct
36 Correct 814 ms 124888 KB Output is correct
37 Correct 787 ms 141980 KB Output is correct
38 Correct 737 ms 163540 KB Output is correct
39 Correct 836 ms 206296 KB Output is correct
40 Correct 815 ms 109244 KB Output is correct
41 Correct 724 ms 159928 KB Output is correct
42 Correct 918 ms 210264 KB Output is correct
43 Correct 649 ms 147928 KB Output is correct
44 Correct 798 ms 154708 KB Output is correct
45 Correct 387 ms 172804 KB Output is correct
46 Correct 459 ms 118996 KB Output is correct
47 Correct 1 ms 344 KB Output is correct
48 Correct 1 ms 344 KB Output is correct
49 Correct 379 ms 68304 KB Output is correct
50 Correct 362 ms 68100 KB Output is correct
51 Correct 380 ms 68292 KB Output is correct
52 Correct 439 ms 68084 KB Output is correct
53 Correct 375 ms 68112 KB Output is correct
54 Correct 374 ms 68380 KB Output is correct
55 Correct 224 ms 68420 KB Output is correct
56 Correct 67 ms 64196 KB Output is correct
57 Correct 448 ms 223240 KB Output is correct
58 Correct 417 ms 172780 KB Output is correct
59 Correct 429 ms 121760 KB Output is correct
60 Correct 201 ms 101312 KB Output is correct
61 Correct 198 ms 100524 KB Output is correct
62 Correct 315 ms 103792 KB Output is correct
63 Correct 296 ms 102768 KB Output is correct
64 Correct 143 ms 70740 KB Output is correct
65 Correct 203 ms 67904 KB Output is correct
66 Correct 270 ms 176632 KB Output is correct
67 Correct 313 ms 178752 KB Output is correct
68 Correct 253 ms 121936 KB Output is correct
69 Correct 289 ms 123764 KB Output is correct
70 Correct 216 ms 124336 KB Output is correct
71 Correct 156 ms 121720 KB Output is correct
72 Correct 249 ms 123324 KB Output is correct
73 Correct 387 ms 222184 KB Output is correct
74 Correct 445 ms 223464 KB Output is correct
75 Correct 434 ms 223340 KB Output is correct
76 Correct 212 ms 80376 KB Output is correct
77 Correct 98 ms 65360 KB Output is correct
78 Correct 279 ms 74316 KB Output is correct
79 Correct 99 ms 66052 KB Output is correct
80 Correct 314 ms 69416 KB Output is correct
81 Correct 959 ms 87120 KB Output is correct
82 Correct 944 ms 87112 KB Output is correct
83 Correct 984 ms 86544 KB Output is correct
84 Correct 1029 ms 86920 KB Output is correct
85 Correct 1004 ms 85468 KB Output is correct
86 Correct 878 ms 85008 KB Output is correct
87 Correct 643 ms 87792 KB Output is correct
88 Correct 1462 ms 97148 KB Output is correct
89 Correct 1139 ms 93040 KB Output is correct
90 Correct 1008 ms 93208 KB Output is correct
91 Correct 121 ms 71920 KB Output is correct
92 Correct 428 ms 125224 KB Output is correct
93 Correct 410 ms 122840 KB Output is correct
94 Correct 620 ms 133852 KB Output is correct
95 Correct 701 ms 130436 KB Output is correct
96 Correct 395 ms 89432 KB Output is correct
97 Correct 467 ms 83448 KB Output is correct
98 Correct 364 ms 190632 KB Output is correct
99 Correct 566 ms 195184 KB Output is correct
100 Correct 357 ms 135784 KB Output is correct
101 Correct 508 ms 142068 KB Output is correct
102 Correct 348 ms 140628 KB Output is correct
103 Correct 236 ms 136284 KB Output is correct
104 Correct 463 ms 147244 KB Output is correct
105 Correct 414 ms 98236 KB Output is correct
106 Correct 131 ms 74568 KB Output is correct
107 Correct 718 ms 100252 KB Output is correct
108 Correct 219 ms 80720 KB Output is correct
109 Correct 603 ms 85584 KB Output is correct