Submission #848415

#	Time	Username	Problem	Language	Result	Execution time	Memory
848415		Muaath_5	Overtaking (IOI23_overtaking)	C++17	65 / 100	3599 ms	15520 KiB

overtaking

#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

const ll N = 1005, INF = 7e15;

ll n, m, l, x;
ll pos[N][N];
ll full[N][N];
vector<int> srt[N];
vector<int> spd;
vector<ll> st;
vector<int> len;



ll tmp;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
	n = N, m = M, l = L, x = X, spd = W, st = T, len = S;
	for (int j = 0; j < n; j++) {
		pos[0][j] = T[j];
		//full[0][j] = T[j];
		srt[0].push_back(j);
	}
	sort(srt[0].begin(), srt[0].end(), [](int x, int y) {
		return st[x] == st[y] ? spd[x] < spd[y] : st[x] < st[y];
	});
	for (int i = 0; i < m-1; i++) {
		//cerr << "Station " << i + 1 << '\n';
		pos[i + 1][srt[i][0]] = 1ll * spd[srt[i][0]] * (len[i + 1] - len[i]) + pos[i][srt[i][0]];
		//full[i + 1][srt[i][0]] = 1ll * spd[srt[i][0]] * (len[i + 1] - len[i]) + full[i][srt[i][0]];
        srt[i + 1].push_back(0);
		//cerr << "Bus " << srt[i][0] << " Arrives " << pos[i+1][srt[i][0]] << '\n';
		for (int j = 1; j < n; j++) {
            srt[i + 1].push_back(j);
			//full[i + 1][srt[i][j]] = 1ll * spd[srt[i][j]] * (len[i + 1] - len[i]) + full[i][srt[i][j]];
            const ll exp = 1ll * spd[srt[i][j]] * (len[i + 1] - len[i]) + pos[i][srt[i][j]];
            if (exp < pos[i + 1][srt[i][j - 1]]) {
				pos[i + 1][srt[i][j]] = pos[i + 1][srt[i][j - 1]];
				//cerr << "Intersects: ";
			}
			else {
				pos[i + 1][srt[i][j]] = exp;
			}
			//cerr << "Bus " << srt[i][j] << " Arrives " << pos[i + 1][srt[i][j]] << '\n';
		}
        tmp = i+1;
		sort(srt[i+1].begin(), srt[i+1].end(), [](int x, int y) {
			return pos[tmp][x] == pos[tmp][y] ? spd[x] < spd[y] : pos[tmp][x] < pos[tmp][y];
		});
	}
}

ll arrival_time(ll Y) {
	ll tm = Y;
	for (int i = 0; i < m-1; i++) {
		const ll exp = 1ll * x * (len[i + 1] - len[i]) + tm;
		if (pos[i][srt[i][0]] >= tm) {
			tm = exp;
		}
		else {
			int l = 0, r = n - 1;
			while (l < r) {
				const int md = (l + r + 1) / 2;
				if (pos[i][srt[i][md]] < tm || (pos[i][srt[i][md]] == tm && spd[srt[i][md]] < x))
					l = md;
				else
					r = md - 1;
			}
			int prv = srt[i][l];
			if (exp < pos[i + 1][prv]) {
				tm = pos[i + 1][prv];
			}
			else {
				tm = exp;
			}
		}
	}
	return tm;
}

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