Submission #1076970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076970		AmirAli_H1	Overtaking (IOI23_overtaking)	C++17	100 / 100	1810 ms	78252 KiB

overtaking

// In the name of Allah

#include <bits/stdc++.h>
#include "overtaking.h"
using namespace std;

typedef			long long				ll;
typedef			pair<int, int>			pii;
typedef			pair<ll, ll>			pll;

#define			F						first
#define			S						second
#define			endl					'\n'
#define			sep						' '
#define			pb						push_back
#define			Mp						make_pair
#define			all(x)					(x).begin(),(x).end()
#define			len(x)					((ll) (x).size())

const int maxn = 1000 + 4;
const int maxs = (1 << 20) + 4;
const ll oo = 8e18 + 4;

int n, m; ll L, X;
pll A[maxn]; ll R[maxn]; int ind;
ll dp[maxn][maxn]; vector<ll> arr;
ll val[maxn][maxn]; vector<ll> ls[maxn];
pii t[2 * maxs];

bool cmp(int i, int j) {
	return (dp[ind][i] < dp[ind][j]);
}

int GI(ll x) {
	return lower_bound(all(arr), x) - arr.begin();
}

int GIx(int i, ll x) {
	return lower_bound(all(ls[i]), x) - ls[i].begin();
}

void build(int v, int tl, int tr) {
	t[v] = Mp(m, n);
	if (tr - tl == 1) return ;
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
}

void set_min(int v, int tl, int tr, int l, int r, pii x) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	if (l == tl && r == tr) {
		t[v] = min(t[v], x);
		return ;
	}
	int mid = (tl + tr) / 2;
	set_min(2 * v + 1, tl, mid, l, r, x); set_min(2 * v + 2, mid, tr, l, r, x);
}

pii get_min(int v, int tl, int tr, int i) {
	if (i >= tr || i < tl) return Mp(m, n);
	if (tr - tl == 1) return t[v];
	int mid = (tl + tr) / 2;
	return min(t[v], min(get_min(2 * v + 1, tl, mid, i), get_min(2 * v + 2, mid, tr, i)));
}

void init(int Lx, int Nx, vector<ll> T, vector<int> W, int Z, int Mx, vector<int> S) {
	L = Lx; n = Nx; m = Mx; X = Z;
	
	for (int i = 0; i < m; i++) R[i] = S[i];
	int j = 0;
	for (int i = 0; i < n; i++) {
		if (W[i] - X <= 0) continue;
		A[j] = Mp(T[i], W[i] - X); j++;
	}
	n = j;
	
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (i == 0) dp[i][j] = A[j].F;
			else {
				dp[i][j] = (dp[i - 1][j] + (R[i] - R[i - 1]) * A[j].S);
			}
		}
		if (i - 1 >= 0) {
			ind = i - 1;
			arr.clear(); arr.resize(n);
			iota(all(arr), 0); sort(all(arr), cmp);
			ll x1 = -oo, x2 = -oo;
			for (int r = 1; r < n; r++) {
				int j1 = arr[r - 1], j2 = arr[r];
				x2 = max(x2, dp[i][j1]);
				if (dp[i - 1][j1] != dp[i - 1][j2]) x1 = x2;
				dp[i][j2] = max(dp[i][j2], x1);
			}
		}
	}
	
	arr.clear(); arr.pb(oo);
	for (int i = 0; i < m; i++) {
		ls[i].clear();
		for (int j = 0; j < n; j++) {
			arr.pb(dp[i][j]);
			ls[i].pb(dp[i][j]);
		}
		sort(all(ls[i])); ls[i].resize(unique(all(ls[i])) - ls[i].begin());
	}
	sort(all(arr)); arr.resize(unique(all(arr)) - arr.begin());
	
	build(0, 0, len(arr));
	for (int i = m - 1; i >= 0; i--) {
		for (int j = 0; j < n; j++) {
			if (i + 1 < m) {
				int lx = GI(dp[i][j] + 1), rx = GI(dp[i + 1][j] + 1);
				set_min(0, 0, len(arr), lx, rx, Mp(i + 1, -GIx(i + 1, dp[i + 1][j])));
			}
		}
		for (int j = 0; j < len(ls[i]); j++) {
			pii x = get_min(0, 0, len(arr), GI(ls[i][j])); x.S = -x.S;
			if (x.F == m) val[i][j] = ls[i][j];
			else val[i][j] = val[x.F][x.S];
		}
	}
	
	return ;
}

ll arrival_time(ll Y) {
	ll res = 0;
	pii x = get_min(0, 0, len(arr), GI(Y)); x.S = -x.S;
	if (x.F == m) res = Y;
	else res = val[x.F][x.S];
	res += (L * X);
	return res;
}

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