Submission #978226

#	Time	Username	Problem	Language	Result	Execution time	Memory
978226		model_code	Escape Route 2 (JOI24_escape2)	C++17	100 / 100	1462 ms	266940 KiB

Main

#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 / 6
• Subtask 2: 8 / 8
• Subtask 3: 17 / 17
• Subtask 4: 23 / 23
• Subtask 5: 36 / 36
• Subtask 6: 10 / 10