Submission #1067056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067056		Gromp15	Overtaking (IOI23_overtaking)	C++17	100 / 100	2858 ms	346780 KiB

overtaking

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#include "overtaking.h"
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

struct seg {
	int N; vector<int> tree, lazy;
	seg() {}
	seg(int n) : N(1<<(__lg(n)+1)), tree(2*N, -1), lazy(2*N, -1) {}
	void push(int node) {
		if (~lazy[node]) {
			tree[node] = lazy[node];
			if (node < N) lazy[node*2] = lazy[node*2+1] = lazy[node];
			lazy[node] = -1;
		}
	}
	void update(int node, int nl, int nr, int ql, int qr, int v) {
		push(node);
		if (ql > nr || qr < nl) return;
		if (ql <= nl && nr <= qr) {
			lazy[node] = v; return;
		}
		int mid = (nl+nr)/2;
		update(node*2, nl, mid, ql, qr, v);
		update(node*2+1, mid+1, nr, ql, qr, v);
	}
	int query(int node, int nl, int nr, int ql, int qr) {
		push(node);
		if (ql > nr || qr < nl) return 0;
		if (ql <= nl && nr <= qr) return tree[node];
		int mid = (nl+nr)/2;
		return query(node*2, nl, mid, ql, qr) + query(node*2+1, mid+1, nr, ql, qr);
	}
};

int L, N, X, M;
vector<ll> T;
vector<int> W, S;

vector<vector<ar<ll, 2>>> cars;
vector<vector<ar<ll, 4>>> go;
vector<ar<ll, 5>> tot, tot2, tot3;
vector<ar<ll, 2>> cov;
vector<ll> coords;

const ll INF = 4e18;
seg st;

void init(int _L, int _N, std::vector<long long> _T, std::vector<int> _W, int _X, int _M, std::vector<int> _S)
{
	L = _L;
	N = _N;
	T = _T;
	W = _W;
	X = _X;
	M = _M;
	S = _S;
	W.push_back(X);
	vector<ar<ll, 2>> buses;
	for (int i = 0; i < N; i++) if (W[i] > X) buses.push_back({T[i], i});
	cars.resize(M), go.resize(M);
	for (int i = 0; i < M - 1; i++) {
		vector<ar<ll, 3>> ints;
		for (auto [x, y] : buses) {
			ints.push_back({x, x + (ll)W[y] * (S[i+1] - S[i]), y});
		}
		sort(all(ints));
		ll to = 0;
		vector<ar<ll, 2>> buses2;
		vector<ar<ll, 2>> tmp;
		for (auto [l, r, idx] : ints) {
			ckmax(to, r);
			buses2.push_back({to, idx});
			tmp.push_back({l, to});
		}
		swap(buses, buses2);
		cars[i] = tmp;
	}
	for (int i = 0; i < M-1; i++) {
		ll R = -1;
		vector<ar<ll, 2>> nw;
		sort(all(cars[i]), [&](const auto &A, const auto &B) { return A[0] != B[0] ? A[0] < B[0] : A[1] > B[1]; });
		for (auto [l, r] : cars[i]) {
			if (r <= R) continue;
			R = r;
			nw.push_back({l, r});
		}
		swap(cars[i], nw);
	}
	vector<ar<ll, 4>> cur;
	for (int i = M-2; i >= 0; i--) {
		ll cur_dist = (ll)(S[i+1] - S[i]) * X;
		assert(is_sorted(all(cars[i])));
		vector<ar<ll, 3>> ints;
		for (int j = 0; j < sz(cars[i]); j++) {
			ll nxt = j+1 < sz(cars[i]) ? cars[i][j+1][0] : cars[i][j][1];
			ll right = min(cars[i][j][1] - cur_dist, nxt);
			if (cars[i][j][0] + 1 <= right) ints.push_back({cars[i][j][0] + 1, right, cars[i][j][1]});
		}
		for (auto [l, r, dest] : ints) go[i].push_back({l, r, dest, i+1});
	}
	for (int i = 0; i < M-1; i++) {
		ll to = (ll)(S[i] - S[0]) * X;
		for (auto [l, r, dest, idx] : go[i]) {
			tot.push_back({l - to, r - to, dest - (ll)(S[idx] - S[0]) * X, idx, i});
			coords.emplace_back(l - to);
			coords.emplace_back(r - to);
			coords.emplace_back(l - to - 1);
			coords.emplace_back(r - to - 1);
			coords.emplace_back(l - to + 1);
			coords.emplace_back(r - to + 1);
			coords.emplace_back(dest - (ll)(S[idx] - S[0]) * X);
		}
	}
	sort(all(coords));
	coords.erase(unique(all(coords)), coords.end());
	auto compress = [&](ll x) {
		return lower_bound(all(coords), x) - coords.begin();
	};
	tot2 = tot;
	for (auto &[l, r, dest, idx, who] : tot2) {
		l = compress(l);
		r = compress(r);
		dest = compress(dest);
	}
	tot3 = tot;
	sort(all(tot3), [&](const auto &A, const auto &B) { return A[0] != B[0] ? A[0] < B[0] : A[1] > B[1]; });
	ll to = -1;
	for (auto [l, r, dest, idx, who] : tot3) {
		if (ckmax(to, r)) {
			cov.push_back({l, to});
		}
	}

	st = seg(sz(coords));

	for (int i = sz(tot2)-1; i >= 0; i--) {
		int L = i;
		while (L && tot2[L-1][3] == tot2[L][3]) L--;
		vector<ar<int, 3>> upds;
		for (int j = L; j <= i; j++) {
			auto [l, r, dest, idx, who] = tot2[j];
			assert(idx == who + 1);
			int val = st.query(1, 0, st.N-1, dest, dest);
			if (val == -1) {
				upds.push_back({l, r, dest});
			}
			else {
				upds.push_back({l, r, val});
			}
		}
		i = L;
		sort(all(upds));
		for (int i = 1; i < sz(upds); i++) assert(upds[i-1][1] < upds[i][0]);
		for (auto [l, r, x] : upds) { 
			st.update(1, 0, st.N-1, l, r, x);
		}
	}
}


long long arrival_time(long long Y)
{
	auto it = upper_bound(all(cov), ar<ll, 2>{Y, INF});
	if (it == cov.begin() || (*prev(it))[1] < Y) {
		return Y + (ll)(S[M-1] - S[0]) * X;
	}
	Y = lower_bound(all(coords), Y) - coords.begin();
	Y = st.query(1, 0, st.N-1, Y, Y);
	return coords[Y] + (ll)(S[M-1] - S[0]) * X;
}

Compilation message (stderr)

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:151:21: warning: narrowing conversion of 'l' from 'std::tuple_element<0, std::array<long long int, 5> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
  151 |     upds.push_back({l, r, dest});
      |                     ^
overtaking.cpp:151:24: warning: narrowing conversion of 'r' from 'std::tuple_element<1, std::array<long long int, 5> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
  151 |     upds.push_back({l, r, dest});
      |                        ^
overtaking.cpp:151:27: warning: narrowing conversion of 'dest' from 'std::tuple_element<2, std::array<long long int, 5> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
  151 |     upds.push_back({l, r, dest});
      |                           ^~~~
overtaking.cpp:154:21: warning: narrowing conversion of 'l' from 'std::tuple_element<0, std::array<long long int, 5> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
  154 |     upds.push_back({l, r, val});
      |                     ^
overtaking.cpp:154:24: warning: narrowing conversion of 'r' from 'std::tuple_element<1, std::array<long long int, 5> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
  154 |     upds.push_back({l, r, val});
      |                        ^

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 26 / 26
• Subtask 5: 35 / 35