結果
問題 | No.777 再帰的ケーキ |
ユーザー |
|
提出日時 | 2024-11-29 15:32:59 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 251 ms / 2,000 ms |
コード長 | 1,535 bytes |
コンパイル時間 | 2,955 ms |
コンパイル使用メモリ | 265,736 KB |
実行使用メモリ | 22,192 KB |
最終ジャッジ日時 | 2024-11-29 15:33:06 |
合計ジャッジ時間 | 6,067 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
ソースコード
#ifndef LOCAL#include <bits/stdc++.h>using namespace std;#define debug(...) (void(0))#else#include "algo/debug.h"#endif#include <atcoder/segtree>using S = int64_t;S op(S a, S b) { return max(a, b); }S e() { return 0; }template <class T>vector<T> compressed(const vector<T>& A) {vector<T> cc;for (const auto& x : A) cc.push_back(x);sort(cc.begin(), cc.end());cc.erase(unique(cc.begin(), cc.end()), cc.end());vector<T> res(A.size());for (unsigned i{}; i < A.size(); i++) res[i] = distance(cc.begin(), lower_bound(cc.begin(), cc.end(), A[i]));return res;}void solve() {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];A = compressed(A);B = compressed(B);vector<vector<pair<int, int>>> Qs(N);for (int i = 0; i < N; i++) Qs[A[i]].push_back({B[i], C[i]});atcoder::segtree<S, op, e> seg(N);for (int i = N; i--; )if (!Qs[i].empty()) {vector<pair<S, int>> res;res.reserve(Qs[i].size());for (const auto& [b, c] : Qs[i]) {S val = seg.prod(b + 1, N);res.push_back({val + c, b});}for(const auto&[val, id]: res) {seg.set(id, op(seg.get(id), val));}}cout << seg.all_prod() << endl;}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int tt = 1;// std::cin >> tt;while (tt--) {solve();}}