結果
問題 | No.777 再帰的ケーキ |
ユーザー |
![]() |
提出日時 | 2022-04-23 16:27:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 455 ms / 2,000 ms |
コード長 | 1,875 bytes |
コンパイル時間 | 2,335 ms |
コンパイル使用メモリ | 211,748 KB |
最終ジャッジ日時 | 2025-01-28 21:12:51 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct segment_tree{int N;vector<long long> ST;segment_tree(int N2){N = 1;while (N < N2){N *= 2;}ST = vector<long long>(N * 2 - 1, 0);}long long operator [](int i){return ST[N - 1 + i];}void update(int i, long long x){i += N - 1;ST[i] = x;while (i > 0){i = (i - 1) / 2;ST[i] = max(ST[i * 2 + 1], ST[i * 2 + 2]);}}long long range_max(int L, int R, int i, int l, int r){if (r <= L || R <= l){return 0;} else if (L <= l && r <= R){return ST[i];} else {int m = (l + r) / 2;return max(range_max(L, R, i * 2 + 1, l, m), range_max(L, R, i * 2 + 2, m, r));}}long long range_max(int L, int R){return range_max(L, R, 0, 0, N);}};int main(){int N;cin >> N;vector<int> A(N), B(N), C(N);for (int i = 0; i < N; i++){cin >> A[i] >> B[i] >> C[i];}vector<int> A2 = A;sort(A2.begin(), A2.end());A2.erase(unique(A2.begin(), A2.end()), A2.end());for (int i = 0; i < N; i++){A[i] = lower_bound(A2.begin(), A2.end(), A[i]) - A2.begin();}vector<int> B2 = B;sort(B2.begin(), B2.end());B2.erase(unique(B2.begin(), B2.end()), B2.end());for (int i = 0; i < N; i++){B[i] = lower_bound(B2.begin(), B2.end(), B[i]) - B2.begin();}int cnt1 = A2.size();int cnt2 = B2.size();vector<vector<pair<int, int>>> Q(cnt2);for (int i = 0; i < N; i++){Q[B[i]].push_back(make_pair(A[i], C[i]));}segment_tree ST(cnt1);for (int i = 0; i < cnt2; i++){int cnt = Q[i].size();sort(Q[i].begin(), Q[i].end(), greater<pair<int, int>>());for (int j = 0; j < cnt; j++){ST.update(Q[i][j].first, max(ST[Q[i][j].first], ST.range_max(0, Q[i][j].first) + Q[i][j].second));}}cout << ST.range_max(0, cnt1) << endl;}