Submission #347379

#	Time	Username	Problem	Language	Result	Execution time	Memory
347379		markthitrin	Salesman (IOI09_salesman)	C++14	60 / 100	1358 ms	65536 KiB

salesman

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
long long max_range = 500001;
class name {
public:
	long long value;
	long long pos;
	long long time;
	bool operator<(const name b) const {
		if (time != b.time)
			return time < b.time;
		return pos < b.pos;
	}
};
long long dpleft[500005]; // let data 0 be the wosrt;
long long dpright[500005];
long long segleft[1100000];
long long segright[1100000];
name a[500005];
long long dp[500005];// actual value;
long long N, U, D, S; // U for left , D  for right;  
void change(long long* seg, long long* data, long long pos, long long number, long long left = 1, long long right = max_range, long long i = 1) {
	if (left == right) {
		data[pos] = number;
		seg[i] = pos;
		return;
	}
	long long mid = (right + left) / 2;
	if (pos <= mid) {
		change(seg, data, pos, number, left, mid, 2 * i);
		seg[i] = seg[2 * i + 1];
		if (data[seg[2 * i]] > data[seg[i]])
			seg[i] = seg[2 * i];
		return;
	}
	else {
		change(seg, data, pos, number, mid + 1, right, 2 * i + 1);
		seg[i] = seg[2 * i];
		if (data[seg[2 * i + 1]] > data[seg[i]])
			seg[i] = seg[2 * i + 1];
		return;
	}
}
long long get_max(long long* seg, long long* data, long long s, long long e, long long left = 1, long long right = max_range, long long i = 1) {
	if (left >= s && right <= e)
		return seg[i];
	else if (left > e || right < s)
		return 0;
	long long mid = (right + left) / 2;
	long long get1, get2;
	get1 = get_max(seg, data, s, e, left, mid, 2 * i);
	get2 = get_max(seg, data, s, e, mid + 1, right, 2 * i + 1);
	if (data[get1] > data[get2])
		return get1;
	return get2;
}
void set_up(long long* seg, long long* data, long long left = 1, long long right = max_range, long long i = 1) {
	if (left == right) {
		seg[i] = left;
		return;
	}
	long long mid = (right + left) / 2;
	set_up(seg, data, left, mid, 2 * i);
	set_up(seg, data, mid + 1, right, 2 * i + 1);
	if (data[seg[2 * i]] > data[seg[2 * i + 1]])
		seg[i] = seg[2 * i];
	else seg[i] = seg[2 * i + 1];
}
void func(long long start, long long end) {
	if (end - start == 1) {
		long long max = dp[a[start].pos];
		long long get_pos_right = get_max(segright, dpright, 1, a[start].pos - 1);
		long long get_pos_left = get_max(segleft, dpleft, a[start].pos + 1, max_range);
		max = std::max(max, dp[get_pos_right] - std::abs(a[start].pos - get_pos_right) * D);
		max = std::max(max, dp[get_pos_left] - std::abs(a[start].pos - get_pos_left) * U);
		//std::cout << "get pos : " << get_pos_right << " " << get_pos_left << "\n";
		dp[a[start].pos] = max + a[start].value;
		change(segright, dpright, a[start].pos, dp[a[start].pos] - (max_range - a[start].pos) * D);
		change(segleft, dpleft, a[start].pos, dp[a[start].pos] - a[start].pos * U);
	}
	else {
		// has finished
		std::vector<long long> changing_number;
		for (int q = start; q < end; q++) {
			long long max = dp[a[q].pos];
			long long get_pos_right = get_max(segright, dpright, 1, a[q].pos - 1);
			long long get_pos_left = get_max(segleft, dpleft, a[q].pos + 1, max_range);
			max = std::max(max, dp[get_pos_right] - std::abs(a[q].pos - get_pos_right) * D);
			max = std::max(max, dp[get_pos_left] - std::abs(a[q].pos - get_pos_left) * U);
			//std::cout << "get pos : " << get_pos_right << " " << get_pos_left << "\n";
			changing_number.push_back(max + a[q].value);
		}
		for (int q = start; q < end; q++) {
			change(segright, dpright, a[q].pos, changing_number[q] - (max_range - a[q].pos) * D);
			change(segleft, dpleft, a[q].pos, changing_number[q] - a[q].pos * U);
		}
		std::vector<long long> max1;
		std::vector<long long> max2;
		max1.push_back(dp[a[start].pos]);
		max2.push_back(dp[a[end - 1].pos]);
		for (int q = start + 1; q < end; q++) {
			long long max = dp[a[q].pos];
			long long get_pos_right = get_max(segright, dpright, 1, a[q].pos - 1);
			max = std::max(max, dp[get_pos_right] - std::abs(a[q].pos - get_pos_right) * D);
			//std::cout << "get pos : " << get_pos_right << " " << get_pos_left << "\n";
			max1.push_back(max + a[q].value);
			change(segright, dpright, a[q].pos, dp[a[q].pos] - (max_range - a[q].pos) * D);
		}
		for (int q = end - 2; q >= start; q--) {
			long long max = dp[a[q].pos];
			long long get_pos_left = get_max(segleft, dpleft, a[q].pos + 1, max_range);
			max = std::max(max, dp[get_pos_left] - std::abs(a[q].pos - get_pos_left) * U);
			//std::cout << "get pos : " << get_pos_right << " " << get_pos_left << "\n";
			max2.push_back(max + a[q].value);
			change(segleft, dpleft, a[q].pos, dp[a[q].pos] - a[q].pos * U);
		}
		int i = 0;
		int j = max2.size() - 1;
		for (int q = start; q < end; q++) {
			long long max = std::max(max1[i], max2[j]);
			dp[a[q].pos] = max;
			change(segright, dpright, a[q].pos, dp[a[q].pos] - (max_range - a[q].pos) * D);
			change(segleft, dpleft, a[q].pos, dp[a[q].pos] - a[q].pos * U);
			++i; --j;
		}
	}
}
int main() {
	std::cin.sync_with_stdio(false);
	std::cin.tie(0);
	std::cin >> N >> U >> D >> S;
	for (long long q = 0; q < N; q++) {
		std::cin >> a[q].time >> a[q].pos >> a[q].value;
	}
	// set up
	std::sort(a, a + N);
	dpright[0] = -100000000000;
	dpleft[0] = -100000000000;
	dp[0] = -100000000000;
	for (long long q = 1; q <= max_range; q++) {
		if (q < S) {
			dp[q] = std::abs(q - S) * -U;
		}
		else if (q > S) {
			dp[q] = std::abs(q - S) * -D;
		}
	}
	for (long long q = 1; q <= max_range; q++) {
		dpleft[q] = dp[q] - q * U;
		dpright[q] = dp[q] - (max_range - q) * D;
	}
	set_up(segleft, dpleft);
	set_up(segright, dpright);
	// dinamic programming;
	long long start = 0;
	long long end = 0;
	while (end != N) {
		while (a[end].time == a[start].time)
			++end;
		func(start, end);
		start = end;
	}
	long long the_result = dp[S];
	for (long long q = 1; q <= max_range; q++) {
		if (q < S) {
			the_result = std::max(the_result, dp[q] - D * std::abs(q - S));
		}
		else {
			the_result = std::max(the_result, dp[q] - U * std::abs(q - S));
		}
	}
	std::cout << the_result;
	return 0;
}

• Subtask 1: 60 / 100