Submission #848996

#	Time	Username	Problem	Language	Result	Execution time	Memory
848996		rainboy	Overtaking (IOI23_overtaking)	C++17	100 / 100	480 ms	46936 KiB

overtaking

#include "overtaking.h"

using namespace std;

typedef vector<int> vi;
typedef vector<long long> vl;

const int N = 1000, M = 1000;

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int n, m, a;

int aa[N]; long long bb[N]; int ii[N];
long long xx[M];

long long eval(int i, int x) {
	return (long long) aa[i] * x + bb[i];
}

int compare_ba(int i, int j) {
	return bb[i] != bb[j] ? (bb[i] < bb[j] ? -1 : 1) : aa[i] - aa[j];
}

int compare_a(int i, int j) {
	return aa[i] - aa[j];
}

int (*compare)(int, int);

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
		while (j < k) {
			int c = compare(ii[j], i_);
			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

long long yy[M][N], dp[M][N];

int shoot(int h, int i, long long b) {
	int lower = h, upper = m;
	while (upper - lower > 1) {
		h = (lower + upper) / 2;
		if ((long long) a * xx[h] + b > yy[h][i])
			lower = h;
		else
			upper = h;
	}
	return upper;
}

void init(int l, int n_, vl bb_, vi aa_, int a_, int m_, vi xx_) {
	n = 0, m = m_, a = a_;
	for (int i = 0; i < n_; i++)
		if (aa_[i] > a_)
			aa[n] = aa_[i], bb[n] = bb_[i], n++;
	for (int h = 0; h < m; h++)
		xx[h] = xx_[h];
	for (int i = 0; i < n; i++)
		ii[i] = i;
	compare = compare_ba, sort(ii, 0, n);
	for (int i = 0; i < n; i++)
		yy[0][i] = bb[ii[i]];
	for (int h = 1; h < m; h++) {
		for (int i = 0, j; i < n; i = j) {
			j = i + 1;
			long long z = eval(ii[i], xx[h]);
			while (j < n && eval(ii[j], xx[h]) <= z)
				bb[ii[j]] = z - (long long) aa[ii[j]] * xx[h], j++;
			compare = compare_a, sort(ii, i, j);
		}
		for (int i = 0; i < n; i++)
			yy[h][i] = eval(ii[i], xx[h]);
	}
	for (int h = m - 1; h >= 0; h--)
		for (int i = 0; i < n; i++)
			if (i > 0 && yy[h][i] == yy[h][i - 1])
				dp[h][i] = dp[h][i - 1];
			else {
				int h_ = i == 0 ? m : shoot(h, i - 1, yy[h][i] - (long long) a * xx[h]);
				dp[h][i] = h_ == m ? (long long) a * (xx[m - 1] - xx[h]) + yy[h][i] : dp[h_][i - 1];
			}
}

long long arrival_time(long long b) {
	int lower = -1, upper = n;
	while (upper - lower > 1) {
		int i = (lower + upper) / 2;
		if (yy[0][i] < b)
			lower = i;
		else
			upper = i;
	}
	int i = lower, h_ = i == -1 ? m : shoot(0, i, b);
	return h_ == m ? (long long) a * xx[m - 1] + b : dp[h_][i];
}

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