Submission #880581

#	Time	Username	Problem	Language	Result	Execution time	Memory
880581		42kangaroo	Overtaking (IOI23_overtaking)	C++17	65 / 100	3513 ms	26192 KiB

overtaking

//  E. Overtaking

#include<bits/stdc++.h>

using namespace std;


	template<typename T>
	using vv_t = vector<vector<T>>;

	vv_t<pair<long long, int>> arT;
	vv_t<long long> neArT;
	vector<long long> s;
	vector<long long> w;
	long long x;

	void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) {
		// init arT amd meArT
		arT = vv_t<pair<long long, int>>(M - 1, vector<pair<long long, int>>(N));
		neArT = vv_t<long long>(M - 1, vector<long long>(N));
		x = X;
		s = vector<long long>(S.begin(), S.end());
		w = vector<long long>(W.begin(), W.end());
		vector<int> o(N);
		std::iota(o.begin(), o.end(), 0);
		std::sort(o.begin(), o.end(), [&](int l, int r) { return tie(T[l], w[l]) < tie(T[r], w[r]); });
		for (int i = 0; i < N; ++i) {
			arT[0][i] = {T[o[i]], o[i]};
			neArT[0][i] = T[o[i]] + w[o[i]] * (s[1] - s[0]);
			if (i > 0) neArT[0][i] = max(neArT[0][i], neArT[0][i - 1]);
		}
		// for each M
		for (int i = 1; i < M - 1; ++i) {
			// sort bus acording to departure first, speed second
			std::sort(o.begin(), o.end(),
			          [&](int l, int r) {
				          return tie(neArT[i - 1][l], w[arT[i - 1][l].second]) <
				                 tie(neArT[i - 1][r], w[arT[i - 1][r].second]);
			          });
			// go through sorted and compute next arrival time, keep max of others
			for (int j = 0; j < N; ++j) {
				arT[i][j] = {neArT[i - 1][o[j]], arT[i - 1][o[j]].second};
				// make a prefix max array of the next arrival time
				neArT[i][j] = arT[i][j].first + w[arT[i][j].second] * (s[i + 1] - s[i]);
				if (j > 0) neArT[i][j] = max(neArT[i][j], neArT[i][j - 1]);
			}
		}
	}

	long long arrival_time(long long Y) {
		// for all M
		for (int i = 0; i < arT.size(); ++i) {
			// binary search the actual time
			int c = upper_bound(arT[i].begin(), arT[i].end(), Y, [&](long long l, pair<long long, int> r) {
				return tie(l, x) < tie(r.first, w[r.second]);
			}) - arT[i].begin();
			// compute next
			Y += x * (s[i + 1] - s[i]);
			if (c > 0) {
				Y = max(neArT[i][c - 1], Y);
			}
		}
		return Y;
	}

Compilation message (stderr)

overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:52:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<long long int, int>, std::allocator<std::pair<long long int, int> > >, std::allocator<std::vector<std::pair<long long int, int>, std::allocator<std::pair<long long int, int> > > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int i = 0; i < arT.size(); ++i) {
      |                   ~~^~~~~~~~~~~~

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