Submission #964982

#	Time	Username	Problem	Language	Result	Execution time	Memory
964982		fzyzzz_z	Salesman (IOI09_salesman)	C++17	60 / 100	433 ms	44608 KiB

salesman

#include <bits/stdc++.h>
using namespace std; 

using ll = long long; 
#define fs first
#define sc second 

const int N = 500005; 

vector<pair<int, int>> a[N];
int tl[2 * N], tr[2 * N]; 
int ql(int l, int r) {
	int res = -1e9; 
	for (l += N, r += N + 1; l < r; l /= 2, r /= 2) {
		if (l & 1) res = max(res, tl[l++]); 
		if (r & 1) res = max(res, tl[--r]); 
	}
	return res; 
}
int qr(int l, int r) {
	int res = -1e9; 
	for (l += N, r += N + 1; l < r; l /= 2, r /= 2) {
		if (l & 1) res = max(res, tr[l++]); 
		if (r & 1) res = max(res, tr[--r]); 
	}
	return res; 
}
void cl(int x, int v) {
	x += N; if (tl[x] >= v) return; 
	for (tl[x] = v; x > 1; x /= 2) {
		tl[x / 2] = max(tl[x], tl[x ^ 1]); 
	}
}
void cr(int x, int v) {
	x += N; if (tr[x] >= v) return; 
	for (tr[x] = v; x > 1; x /= 2) {
		tr[x / 2] = max(tr[x], tr[x ^ 1]); 
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, lc, rc, s; 
	cin >> n >> lc >> rc >> s; 
	
	for (int i = 0; i < n; ++i) {
		int t, l, x; 
		cin >> t >> l >> x; 
		a[t].push_back({l, x}); 
	}
	a[N - 1].push_back({s, 0}); 

	for (int i = 0; i < N; ++i) {
		sort(a[i].begin(), a[i].end()); 
	}
	for (int i = 0; i < N; ++i) {
		tl[N + i] = tr[N + i] = -1e9; 
		if (i == s) {
			tl[N + i] = i * rc; 
			tr[N + i] = (N - 1 - i) * lc; 
		}
	}
	for (int i = N - 1; i > 0; --i) {
		tr[i] = max(tr[2 * i], tr[2 * i + 1]); 
		tl[i] = max(tl[2 * i], tl[2 * i + 1]); 
	}

	for (int t = 0; t < N; ++t) {
		vector<int> res; 
		int lp = 0, lv = -1e9; 
		for (int i = 0; i < a[t].size(); ++i) {
			int v = lv + a[t][i].sc - (a[t][i].fs - lp) * rc; 
			v = max(v, a[t][i].sc - rc * a[t][i].fs + ql(0, a[t][i].fs));
			res.push_back(v); 
			lv = v; lp = a[t][i].fs; 
		}
		lp = N - 1; lv = -1e9; 
		for (int i = a[t].size() - 1; i >= 0; --i) {
			int v = lv + a[t][i].sc - (lp - a[t][i].fs) * lc; 
			v = max(v, a[t][i].sc - lc * (N - 1 - a[t][i].fs) + qr(a[t][i].fs, N - 1)); 
			lv = v; lp = a[t][i].fs; 
			res[i] = max(res[i], v); 
		}

		for (int i = 0; i < a[t].size(); ++i) {
			cl(a[t][i].fs, res[i] + a[t][i].fs * rc); 
			cr(a[t][i].fs, res[i] + (N - 1 - a[t][i].fs) * lc); 
		}

		// if (res.size()) {
		// 	cout << "! " << t << '\n';
		// 	for (auto x: res) {
		// 		cout << x << ' '; 
		// 	}
		// 	cout << '\n';
		// }
		if (t + 1 == N) {
			cout << res[0] << "\n";
		}
	}



	return 0; 
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for (int i = 0; i < a[t].size(); ++i) {
      |                   ~~^~~~~~~~~~~~~
salesman.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for (int i = 0; i < a[t].size(); ++i) {
      |                   ~~^~~~~~~~~~~~~

• Subtask 1: 60 / 100