oj.uz

Submission #964983

# Submission time Handle Problem Language Result Execution time Memory
964983 2024-04-18T00:34:26 Z fzyzzz_z Salesman (IOI09_salesman) C++17
100 / 100
 569 ms 44584 KB 
#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));
			v = max(v, a[t][i].sc - lc * (N - 1 - a[t][i].fs) + qr(a[t][i].fs, N - 1)); 
			res.push_back(v); 
			lv = v; lp = a[t][i].fs; 
			// cout << v << ' '; 
		}
		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;
			// cout << v << ' '; 
			v = max(v, a[t][i].sc - lc * (N - 1 - a[t][i].fs) + qr(a[t][i].fs, N - 1)); 
			v = max(v, a[t][i].sc - rc * a[t][i].fs + ql(0, a[t][i].fs));
			lv = v; lp = a[t][i].fs; 
			res[i] = max(res[i], v); 
			// cout << 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

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:92: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]
   92 |   for (int i = 0; i < a[t].size(); ++i) {
      |                   ~~^~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19804 KB Output is correct
2 Correct 7 ms 19804 KB Output is correct
3 Correct 7 ms 20056 KB Output is correct
4 Correct 9 ms 20060 KB Output is correct
5 Correct 10 ms 20060 KB Output is correct
6 Correct 29 ms 20828 KB Output is correct
7 Correct 55 ms 22468 KB Output is correct
8 Correct 95 ms 24748 KB Output is correct
9 Correct 153 ms 27060 KB Output is correct
10 Correct 227 ms 34116 KB Output is correct
11 Correct 308 ms 34740 KB Output is correct
12 Correct 424 ms 38624 KB Output is correct
13 Correct 445 ms 38924 KB Output is correct
14 Correct 569 ms 44584 KB Output is correct
15 Correct 442 ms 43480 KB Output is correct
16 Correct 534 ms 43712 KB Output is correct
17 Correct 8 ms 19840 KB Output is correct
18 Correct 8 ms 19804 KB Output is correct
19 Correct 8 ms 20060 KB Output is correct
20 Correct 9 ms 20060 KB Output is correct
21 Correct 8 ms 20096 KB Output is correct
22 Correct 10 ms 20112 KB Output is correct
23 Correct 9 ms 20060 KB Output is correct
24 Correct 11 ms 20056 KB Output is correct
25 Correct 77 ms 22352 KB Output is correct
26 Correct 130 ms 25028 KB Output is correct
27 Correct 219 ms 28504 KB Output is correct
28 Correct 258 ms 29512 KB Output is correct
29 Correct 340 ms 31412 KB Output is correct
30 Correct 334 ms 33304 KB Output is correct