Submission #881608

#	Time	Username	Problem	Language	Result	Execution time	Memory
881608		42kangaroo	Overtaking (IOI23_overtaking)	C++17	39 / 100	191 ms	30772 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<long long> arT;
vector<long long> s;
vector<long long> w;
vv_t<long long> backT;

long long x;


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

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

vector<Val> resV;

int wij(int i, int j, int p) {
	int l = p - 1, r = s.size();
	while (l + 1 < r){
		int m = (l + r)/2;
		if (arT[p][i] + w[i]*(s[m] - s[p]) > arT[p][j] + w[j]*(s[m] - s[p])) r = m;
		else l = m;
	}
	return l;
}

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;
	arT = vv_t<long long>(M - 1, vector<long long>(N));
	neArT = vv_t<long long>(M - 1, vector<long long>(N));
	backT = vv_t<long long>(M, vector<long long>(N));
	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][o[i]] = t[o[i]];
		neArT[0][o[i]] = t[o[i]] + w[o[i]] * (s[1] - s[0]);
		if (i > 0) neArT[0][o[i]] = max(neArT[0][o[i]], neArT[0][o[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[l]) <
			                 tie(neArT[i - 1][r], w[r]);
		          });
		// go through sorted and compute next arrival time, keep max of others
		for (int j = 0; j < N; ++j) {
			arT[i][o[j]] = neArT[i - 1][o[j]];
			// make a prefix max array of the next arrival time
			neArT[i][o[j]] = arT[i][o[j]] + w[o[j]] * (s[i + 1] - s[i]);
			if (j > 0) neArT[i][o[j]] = max(neArT[i][o[j]], neArT[i][o[j - 1]]);
		}
	}
	for (int i = 0; i < N; ++i) {
		backT.back()[i] = neArT.back()[i];
	}
	// sort by arT, w, and then do deque / convex hull opt to find the
	// find cutting point, by binary search on M
	for (int i = M - 2; i >= 0; --i) {
		std::sort(o.begin(), o.end(),
		          [&](int l, int r) {
			          return tie(arT[i][l], w[l]) <
			                 tie(arT[i][r], w[l]);
		          });
		deque<pair<int,int>> st;
		for (int j = 0; j < N; ++j) {
			int po = o[j];
			if (j > 0 && arT[i][po] == arT[i][o[j - 1]]) {
				backT[i][po] = backT[i][o[j - 1]];
			} else {
				int l = -1, r = st.size();
				while (l + 1 < r) {
					int m = (l + r)/2;
					if (arT[i][po] + x*(s[st[m].second] - s[i]) < arT[i][st[m].first]+ w[st[m].first]*(s[st[m].second] - s[i])) l = m;
					else r = m;
				}
				if (l == -1) {
					backT[i][po] = arT[i][po] + x*(s.back() - s[i]);
				} else {
					int ll = i, rr = st[l].second;
					if (l < st.size() - 1) {
						ll = st[l + 1].second;
					}
					while (ll + 1 < rr) {
						int mm = (ll + rr)/2;
						if (arT[i][po] + x*(s[mm] - s[i]) <= arT[i][st[l].first]+ w[st[l].first]*(s[mm] - s[i])) rr = mm;
						else ll = mm;
					}
					backT[i][po] = backT[rr][st[l].first];
				}
			}
			while (!st.empty() && wij(st.back().first, po, i) >= st.back().second) st.pop_back();
			if (!st.empty()) st.push_back({po, wij(st.back().first, po, i)});
			else st.push_back({po, M - 1});
			if (st.back().second <= i) st.pop_back();
		}
	}
	// fill in last line by looking at each highest point in order.
	resV.clear();
	std::sort(o.begin(), o.end(),
	          [&](int l, int r) {
		          return tie(arT[0][l], w[l]) <
		                 tie(arT[0][r], w[r]);
	          });
	deque<pair<int,int>> st;
	for (int i = 0; i < N; ++i) {
		int po = o[i];
		int last = 0;
		while (!st.empty() && wij(st.back().first, po, 0) >= st.back().second) {
			for (int j = last + 1; j <= st.back().second; ++j) {
				if (arT[0][st.back().first] + (w[st.back().first] - x)*(s[j - 1] - s[0]) + 1 > arT[0][po]) break;
				resV.push_back({backT[j][st.back().first], arT[0][st.back().first] + (w[st.back().first] - x)*(s[j - 1] - s[0]) + 1, min(arT[0][st.back().first] + (w[st.back().first] - x)*(s[j] - s[0]), arT[0][po])});
			}
			last = st.back().second;
			st.pop_back();
		}
		if (!st.empty()) {
			for (int j = last + 1; j <= wij(st.back().first, po, 0); ++j) {
				if (arT[0][st.back().first] + (w[st.back().first] - x)*(s[j - 1] - s[0]) + 1 > arT[0][po]) break;
				resV.push_back({backT[j][st.back().first], arT[0][st.back().first] + (w[st.back().first] - x)*(s[j - 1] - s[0]) + 1, min(arT[0][st.back().first] + (w[st.back().first] - x)*(s[j] - s[0]), arT[0][po])});
			}
			st.push_back({po, wij(st.back().first, po, 0)});
		}
		else st.push_back({po, M - 1});
		if (st.back().second <= 0) st.pop_back();
	}
	int last = 0;
	while (!st.empty()) {
		for (int j = last + 1; j <= st.back().second; ++j) {
			resV.push_back({backT[j][st.back().first], arT[0][st.back().first] + (w[st.back().first] - x)*(s[j - 1] - s[0]) + 1, arT[0][st.back().first] + (w[st.back().first] - x)*(s[j] - s[0])});
		}
		last = st.back().second;
		st.pop_back();
	}
}

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

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:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for (int i = 0; i < W.size(); ++i) {
      |                  ~~^~~~~~~~~~
overtaking.cpp:121:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |      if (l < st.size() - 1) {
      |          ~~^~~~~~~~~~~~~~~
overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:180:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Val>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |  if (neP < resV.size() && resV[neP].s <= Y) return resV[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