Submission #1087512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087512		Nonoze	Overtaking (IOI23_overtaking)	C++17	19 / 100	7 ms	1628 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, pref2;
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;
	}
	for (int i=0; i<n; i++) dp[i][m-1]=positions[i][m-1];
	pref.resize(m), pref2.resize(m);
	for (int j=m-1; 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 {
				if (j!=m-1) 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}});
			pref2[j].pb({act, {mxcur, poscur}});
		}
		int mn=1e18; pos=-1;
		for (int tt=n-1; tt>=0; tt--) {
			int i=v[tt].se;
			if (a[i].se<mn) mn=a[i].se, pos=i;
			pref[j][tt].se={mn, pos};
		}
	}
}

int arrival_time(int y) {
	if (!n) return (int)y+x*l;
	int lo=1, r=m-1, 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].end() && lb->se.fi<y) r=mid-1, ans=mid;
		else lo=mid+1;
	}
	if (ans==-1) return (int)y+x*l;
	auto lb=upper_bound(all(pref2[ans-1]), mp(y+x*s[ans-1], mp(-1LL, -1LL))); lb--;
	return dp[lb->se.se][ans];
}

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