Submission #1103772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103772		Nonoze	Overtaking (IOI23_overtaking)	C++17	19 / 100	2 ms	848 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;

int n, m, x;
vector<int> t, w;
vector<signed> s;
vector<vector<int>> dp;
vector<vector<pair<int, int>>> ttime;
vector<int> base;

void init(signed L, signed N, vector<int> T, vector<signed> W, signed X, signed M, vector<signed> S) {
	n=N, m=M, x=X, s=S;
	for (int i=0; i<n; i++) {
		if (W[i]>X) t.pb(T[i]), w.pb(W[i]);
	}
	n=sz(t);
	dp.resize(n, vector<int>(m, 1e18));
	ttime.resize(n, vector<pair<int, int>>(m));
	vector<vector<int>> time2(n, vector<int>(m));
	vector<vector<int>> empl(n, vector<int>(m));
	{
		vector<pair<pair<int, int>, int>> bus;
		for (int i=0; i<n; i++) bus.pb({{t[i], w[i]}, i});
		sort(all(bus));
		for (int i=0; i<n; i++) {
			base.pb(bus[i].fi.fi);
			ttime[i][0]={bus[i].fi.fi, bus[i].se};
		}
	}
	for (int act=1; act<m; act++) {
		vector<pair<pair<int, int>, int>> bus;
		for (int i=0; i<n; i++) bus.pb({{ttime[i][act-1].fi, w[ttime[i][act-1].se]}, ttime[i][act-1].se});
		sort(all(bus));
		int sz=s[act]-s[act-1];
		int latest=0;
		for (int i=0; i<n; i++) {
			int nb=bus[i].fi.fi+sz*bus[i].fi.se;
			cmax(latest, nb);
			ttime[i][act]={latest, bus[i].se};
			time2[bus[i].se][act]=latest;
			empl[bus[i].se][act]=i;
		}
	}
	for (int i=0; i<n; i++) dp[i][m-1]=ttime[i][m-1].fi;
	for (int act=m-2; act>=0; act--) {
		for (int i=0; i<n; i++) {
			if (!i) {
				dp[i][act]=ttime[i][act].fi+x*(L-s[act]);
				continue;
			}
			int l=act+1, r=m-1, ans=-1;
			while (l<=r) {
				int mid=(l+r)/2;
				int posact=ttime[i][act].fi+x*(s[mid]-s[act]);
				int posnxt=ttime[i-1][mid].fi;
				if (posnxt>=posact) {
					ans=mid;
					r=mid-1;
				} else {
					l=mid+1;
				}
			}
			// if (i==2 && act==1) cout << nxt << ' ' << ans << endl;
			if (ans==-1) {
				dp[i][act]=ttime[i][act].fi+x*(L-s[act]);
			} else {
				dp[i][act]=dp[i-1][ans];
			}
		}
	}
	// for (int i=0; i<n; i++) {
	// 	for (int j=0; j<m; j++) {
	// 		cout << ttime[i][j].fi << ',' << dp[i][j] << ' ';
	// 	}
	// 	cout << endl;
	// }
}

int arrival_time(int y) {
	if (!n || base[0]>=y) return y+x*s.back();
	int before=lower_bound(all(base), y)-base.begin()-1;
	int l=0, r=m-1, ans=-1;
	while (l<=r) {
		int mid=(l+r)/2;
		int pos=y+x*s[mid];
		if (ttime[before][mid].fi>=pos) {
			r=mid-1;
			ans=mid;
		} else {
			l=mid+1;
		}
	}
	if (ans==-1) return y+x*s.back();
	// cout << "ans: " << ans << ' ' << before << endl;
	return dp[before][ans];
}

/*

180 130 180 55
0: 30 0
0 0: 60
0 1: 80
0 2: 130
0 3: 180

1: 20 10
1 0: 80
1 1: 80
1 2: 100
1 3: 130

2: 20 40
2 0: 100
2 1: 130
2 2: 180
2 3: 180

3: 5 20
3 0: 80
3 1: 80
3 2: 70
3 3: 55


0
50

*/

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