Submission #880604

#	Time	Username	Problem	Language	Result	Execution time	Memory
880604		42kangaroo	Overtaking (IOI23_overtaking)	C++17	39 / 100	51 ms	16512 KiB

overtaking

//  E. Overtaking

#include<bits/stdc++.h>
#include "overtaking.h"

using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

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

vv_t<long long> neArT;

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

struct Val {
	long long en, s, e;
};

bool operator<(const Val& l, const Val& r) {
	return l.e < r.e;
}

bool operator==(const Val& l, const Val& r){
	return tie(l.s, l.e, l.en) == tie(r.s, r.e, r.en);
}

vv_t<Val> backT;


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 neArT
	vector<bool> val(N, true);
	int nn = N;
	for (int i = 0; i < N; ++i) {
		if (W[i] <= X) {
			val[i] = false;
			nn--;
		}
	}
	N = nn;
	assert(N * M <= 1e5);
	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));
	backT = vv_t<Val>(M);
	for (int i = 0; i < M; ++i) {
		backT[i].reserve(2*N);
	}
	x = X;
	s = vector<long long>(S.begin(), S.end());
	w = vector<long long>(N);
	vector<long long> t(N);
	int ind = 0;
	for (int i = 0; i < W.size(); ++i) {
		if (val[i]) {
			t[ind] = T[i];
			w[ind++] = W[i];
		}
	}
	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 according 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]);
		}
	}
	// go backwards, have the intervals where stuff happens.
	for (int i = 0; i < N; ++i) {
		backT.back().push_back({neArT.back()[i], neArT.back()[i], neArT.back()[i]});
	}
	std::sort(backT.back().begin(), backT.back().end());
	backT.back().erase(std::unique(backT.back().begin(), backT.back().end()), backT.back().end());
	for (int i = M - 2; i >= 0; --i) {
		vector<Val> ne(backT[i + 1].size());
		for (int j = 0; j < ne.size(); ++j) {
			ne[j].en = backT[i + 1][j].en;
			ne[j].e = backT[i + 1][j].e - X*(s[i + 1] - s[i]);
			ne[j].s = backT[i + 1][j].s - X*(s[i + 1] - s[i]);
		}
		for (int j = 0; j < N; ++j) {
			long long pos = neArT[i][j];
			int neP = std::lower_bound(backT[i + 1].begin(), backT[i + 1].end(), pos,
			                           [&](Val l, long long r) { return l.e < r;}) - backT[i + 1].begin();
			if (backT[i + 1][neP].s <= pos) ne[neP].s = min(ne[neP].s, arT[i][j].first + 1);
		}
		int neS = ne.size();
		for (int j = 0; j < N; ++j) {
			long long oP = arT[i][j].first;
			int neO = std::lower_bound(ne.begin(), ne.begin() + neS, oP,
			                           [&](Val l, long long r) { return l.e < r;}) - ne.begin();
			if (ne[neO].s > oP) ne.push_back({oP + x*(s.back() - s[i]), oP, oP});
		}
		std::sort(ne.begin(), ne.end());
		ne.erase(std::unique(ne.begin(), ne.end()), ne.end());
		long long last;
		if (!ne.empty()) {
			backT[i].push_back(ne.back());
			last = ne.back().s;
		}
		for (int j = ne.size() - 2; j >= 0; --j) {
			ne[j].e = min(ne[j].e, last - 1);
			last = min(last, ne[j].s);
			if (ne[j].e >= ne[j].s) {
				backT[i].push_back(ne[j]);
			}
		}
		std::reverse(backT[i].begin(), backT[i].end());
	}
}

long long arrival_time(long long Y) {
	int neP = std::lower_bound(backT.front().begin(), backT.front().end(), Y,
	                          [&](Val l, long long r) { return l.e < r;}) - backT.front().begin();
	if (neP < backT.front().size() && backT.front()[neP].s <= Y) return backT.front()[neP].en;
	return Y + x*(s.back() - s.front());
}
//502032794

Compilation message (stderr)

overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for (int i = 0; i < W.size(); ++i) {
      |                  ~~^~~~~~~~~~
overtaking.cpp:96:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Val, std::allocator<Val> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   for (int j = 0; j < ne.size(); ++j) {
      |                   ~~^~~~~~~~~~~
overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:135:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Val, std::allocator<Val> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |  if (neP < backT.front().size() && backT.front()[neP].s <= Y) return backT.front()[neP].en;
      |      ~~~~^~~~~~~~~~~~~~~~~~~~~~

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