제출 #964982

#제출 시각아이디문제언어결과실행 시간메모리
964982fzyzzz_zSalesman (IOI09_salesman)C++17
60 / 100
433 ms44608 KiB
#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; }

컴파일 시 표준 에러 (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) {
      |                   ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...