Submission #1087467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087467		Nonoze	Overtaking (IOI23_overtaking)	C++17	0 / 100	1 ms	348 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)
#define int long long
using namespace std;

vector<vector<int>> dp;
vector<signed> s;
vector<pair<int, int>> a;
vector<set<pair<pair<int, int>, int>>> t;
vector<vector<pair<int, pair<int, int>>>> pref;
int n, m, x, l;
void init(signed L, signed N, vector<int> T, vector<signed> W, signed X, signed M, vector<signed> S) {
	l=L, n=N, m=M, x=X, s=S;
	for (int i=0; i<n; i++) {
		if (W[i]>x) a.pb({W[i], T[i]});
	}
	sort(rall(a)); n=sz(a);
	dp.resize(n, vector<int>(m, 0)), t.resize(m);
	vector<vector<int>> positions(n, vector<int>(m, 0));
	for (int i=0; i<n; i++) {
		int act=a[i].se;
		for (int j=0; j<m-1; j++) {
			auto lb=lower_bound(all(t[j]), mp(mp(act, -1LL), -1LL));
			int prec=act;
			if (lb==t[j].begin()) act+=a[i].fi*(s[j+1]-s[j]);
			else {
				lb--;
				act=max(act+a[i].fi*(s[j+1]-s[j]), lb->fi.se);
			}
			t[j].insert({{prec, act}, i});
			positions[i][j]=prec;
		}
		positions[i][m-1]=act;
		// cout << act << ' ';
	}
	// cout << endl;
	for (int i=0; i<n; i++) dp[i][m-1]=positions[i][m-1];
	pref.resize(m);
	for (int j=m-2; j>=0; j--) {
		vector<pair<int, int>> v;
		for (int i=0; i<n; i++) v.pb({positions[i][j], i});
		sort(all(v));
		int pos=-1, mxcur=-1, poscur=-1, lst=-1;
		for (auto [act, i]: v) {
			if (lst!=act) pos=poscur;
			if (pos==-1) {
				dp[i][j]=act+(l-s[j])*x;
			}
			else {
				dp[i][j]=max(act+(l-s[j])*x, dp[pos][j+1]);
			}
			t[j].insert({{act, positions[i][j+1]}, i});
			if (positions[i][j+1]>mxcur) mxcur=positions[i][j+1], poscur=i;
			lst=act;
			pref[j].pb({act, {mxcur, poscur}});
		}
	}
	// for (int i=0; i<n; i++) {
	// 	cout << i << ": " << a[i].fi << ' ' << a[i].se << endl;
	// 	for (int j=0; j<m; j++) {
	// 		cout << i << ' ' << j << ": " << dp[i][j] << endl;
	// 	}
	// 	cout << endl;
	// }
	// cout << endl;
}

int arrival_time(int y) {
	if (!n) return (int)y+x*l;
	int lo=0, r=m-2, ans=-1;
	while (lo<=r) {
		int mid=(lo+r)/2;
		int act=y+x*s[mid];
		auto lb=lower_bound(all(pref[mid]), mp(act, mp(-1LL, -1LL)));
		// if (lb!=pref[mid].begin()) {
		// 	cout << mid << ": " << act << " " << prev(lb)->fi << ' ' << prev(lb)->se.fi << ' ' << prev(lb)->se.se << endl;
		// }
		if (lb!=pref[mid].begin() && prev(lb)->se.fi>act) r=mid-1, ans=mid;
		else lo=mid+1;
	}
	if (ans==-1) return (int)y+x*l;
	auto lb=upper_bound(all(pref[ans]), mp(y+x*s[ans], mp(-1LL, -1LL))); lb--;
	// cout << lb->se.se << ' ' << ans << endl;
	return dp[lb->se.se][ans+1];
}

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