Submission #348173

#	Time	Username	Problem	Language	Result	Execution time	Memory
348173		markthitrin	Salesman (IOI09_salesman)	C++14	100 / 100	1802 ms	43160 KiB

salesman

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using ll = long long;
ll max_range = 500002;
class name {
public:
	ll time;
	ll pos;
	ll value;
	bool operator<(const name b) const {
		if (time != b.time)
			return time < b.time;
		return pos < b.pos;
	}
};

ll dp[500005];
ll dpleft[500005];
ll dpright[500005];
ll segleft[1100000];
ll segright[1100000];
name a[500005];
ll N, U, D, S;
void change(ll* seg, ll* data, ll pos, ll number, ll left = 1, ll right = max_range, ll i = 1) {
	if (left == right) {
		seg[i] = pos;
		data[pos] = number;
		return;
	}
	ll mid = (left + right) / 2;
	if (pos <= mid) {
		change(seg, data, pos, number, left, mid, 2 * i);
		seg[i] = seg[2 * i + 1];
		if (data[seg[i]] < data[seg[2 * i]])
			seg[i] = seg[2 * i];
	}
	else {
		change(seg, data, pos, number, mid + 1, right, 2 * i + 1);
		seg[i] = seg[2 * i];
		if (data[seg[i]] < data[seg[2 * i + 1]]) {
			seg[i] = seg[2 * i + 1];
		}
	}
}
ll get_max_pos(ll* seg, ll* data, ll s, ll e, ll left = 1, ll right = max_range, ll i = 1) {
	if (right < left)
		return 0;
	if (left >= s && right <= e) {
		return seg[i];
	}
	if (left > e || right < s) {
		return 0;
	}
	ll mid = (right + left) / 2;
	ll get1 = get_max_pos(seg, data, s, e, left, mid, 2 * i);
	ll get2 = get_max_pos(seg, data, s, e, mid + 1, right, 2 * i + 1);
	if (data[get1] > data[get2])
		return get1;
	return get2;
}
ll set_up(ll* seg, ll* data, ll left = 1, ll right = max_range, ll i = 1) {
	if (left == right) {
		seg[i] = left;
		return seg[i];
	}
	ll mid = (left + right) / 2;
	ll get1 = set_up(seg, data, left, mid, 2 * i);
	ll get2 = set_up(seg, data, mid + 1, right, 2 * i + 1);
	if (data[get1] > data[get2])
		seg[i] = seg[2 * i];
	else seg[i] = seg[2 * i + 1];
	return seg[i];
}
void func(ll start, ll end) {
	if (end - start == 1) {
		ll pos = a[start].pos;
		ll value = a[start].value;
		ll max = dp[pos] + value;
		ll get1 = get_max_pos(segright, dpright, 1, pos - 1);
		ll get2 = get_max_pos(segleft, dpleft, pos + 1, max_range);
		max = std::max(max , dp[get1] - std::abs(get1 - pos) * D + value);
		max = std::max(max, dp[get2] - std::abs(get2 - pos) * U + value);
		dp[pos] = max;
		change(segleft, dpleft, pos, dp[pos] - pos * U);
		change(segright, dpright, pos, dp[pos] - (max_range - pos) * D);
	}
	else {
		std::vector<ll> changing_number;
		for (ll q = start; q < end; q++) {
			ll pos = a[q].pos;
			ll value = a[q].value;
			ll max = dp[pos] + value;
			ll get1 = get_max_pos(segright, dpright, 1, pos - 1);
			ll get2 = get_max_pos(segleft, dpleft, pos + 1, max_range);
			max = std::max(max, dp[get1] - std::abs(get1 - pos) * D + value);
			max = std::max(max, dp[get2] - std::abs(get2 - pos) * U + value);
			changing_number.push_back(max);
		}
		for (ll q = 0; q < changing_number.size(); q++) {
			ll pos = a[q + start].pos;
			dp[pos] = changing_number[q];
		}
		std::vector<ll> u1;
		std::vector<ll> u2;
		ll prev_max = changing_number[0];
		u1.push_back(prev_max);
		for (ll q = start + 1; q < end; q++) {
			ll pos = a[q].pos;
			ll value = a[q].value;
			ll max = dp[pos];
			ll get1 = get_max_pos(segright, dpright, a[q - 1].pos + 1, pos - 1);
			if(std::abs(pos - a[q-1].pos) > 1)
				max = std::max(max, dp[get1] - std::abs(pos - get1) * D + value);
			max = std::max(max, prev_max - std::abs(pos - a[q - 1].pos) * D + value);
			u1.push_back(max);
			prev_max = max;
		}
		prev_max = changing_number.back();
		u2.push_back(prev_max);
		for (ll q = end - 2; q >= start; q--) {
			ll pos = a[q].pos;
			ll value = a[q].value;
			ll max = dp[pos];
			ll get1 = get_max_pos(segleft, dpleft, pos + 1, a[q + 1].pos - 1);
			if(std::abs(a[q + 1].pos -pos) > 1)
				max = std::max(max, dp[get1] - std::abs(get1 - pos) * U + value);
			max = std::max(max, prev_max - std::abs(a[q + 1].pos - pos) * U + value);
			u2.push_back(max);
			prev_max = max;
		}
		for (ll q = 0; q < u1.size(); q++) {
			ll pos = a[start + q].pos;
			dp[pos] = std::max(u1[q], u2[u2.size() - q - 1]);
			change(segleft, dpleft, pos, dp[pos] - pos * U);
			change(segright, dpright, pos, dp[pos] - (max_range - pos) * D);
		}
	}
}
int main() {
	std::cin.sync_with_stdio(false);
	std::cin.tie(0);
	std::cin >> N >> U >> D >> S;
	for (ll q = 0; q < N; q++) {
		std::cin >> a[q].time >> a[q].pos >> a[q].value;
	}
	std::sort(&a[0], &a[N]);
	// let 0 position be the worst case as much as possible
	dp[0] = -100000000000000000ll;
	dpleft[0] = -100000000000000000ll;
	dpright[0] = -100000000000000000ll;
	for (ll 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 (ll q = 1; q <= max_range; q++) {
		dpleft[q] = dp[q] - U * q;
		dpright[q] = dp[q] - (max_range - q) * D;
	}
	set_up(segleft, dpleft);
	set_up(segright, dpright);
	ll start = 0;
	ll end = 0;
	while (end != N) {
		while (a[start].time == a[end].time) {
			++end;
			if (end == N)
				break;
		}
		func(start, end);
		start = end;
	}
	ll result = 0;
	for (ll q = 1; q <= max_range; q++) {
		if (q < S) {
			result = std::max(result, dp[q] - std::abs(q - S) * D);
		}
		else if (q == S) {
			result = std::max(result, dp[q]);
		}
		else {
			result = std::max(result, dp[q] - std::abs(q - S) * U);
		}
	}
	std::cout << result;
	return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'void func(ll, ll)':
salesman.cpp:101:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   for (ll q = 0; q < changing_number.size(); q++) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:133:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |   for (ll q = 0; q < u1.size(); q++) {
      |                  ~~^~~~~~~~~~~

• Subtask 1: 100 / 100