結果
問題 | No.777 再帰的ケーキ |
ユーザー |
![]() |
提出日時 | 2019-05-15 00:45:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 608 ms / 2,000 ms |
コード長 | 2,668 bytes |
コンパイル時間 | 2,277 ms |
コンパイル使用メモリ | 195,736 KB |
実行使用メモリ | 21,420 KB |
最終ジャッジ日時 | 2024-07-20 05:38:17 |
合計ジャッジ時間 | 7,861 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;template< typename T >class segment_tree {const vector<int> coord;const map<int, int> mp;const int sz;const int Sz;vector<T> seg;const function<T(T, T)> o;const T id;public:segment_tree (const vector<int> coord,const function<T(T, T)> o,const T id) :coord([&](){vector<int> v = coord;int p = 1;for (; p < (int)v.size(); p <<= 1) {}v.resize(p, (int)((1LL << 31) - 1));return v;}()),mp([&](){map<int, int> m;int i = 0;for (auto const& e : coord) {m[e] = i++;}return m;}()),sz(coord.size()),Sz(sz << 1),seg(Sz, id),o(o),id(id){}void update (int k, const T& x) {auto it = mp.find(k);assert(it != mp.end());k = it->second;k += sz;seg[k] = x;while(k >>= 1) {seg[k] = o(seg[2 * k], seg[2 * k + 1]);}}void add (int k, const T& x) {update(k, x + seg[k + sz]);}T query (int l, int r) {l = lower_bound(coord.begin(), coord.end(), l) - coord.begin();r = lower_bound(coord.begin(), coord.end(), r) - coord.begin();T L = id, R = id;for(l += sz, r += sz; l < r; l >>= 1, r >>= 1) {if(l & 1) L = o(L, seg[l++]);if(r & 1) R = o(seg[--r], R);}return o(L, R);}T at (int k) const {auto it = mp.find(k);assert(it != mp.end());return seg[it->second + sz];}};int main() {int n;cin >> n;vector<int> coord(n, 0);vector<tuple<int, int, long long>> abc(n);for (int i = 0; i < n; i++) {int a, b; long long c;cin >> a >> b >> c;coord[i] = b;abc[i] = make_tuple(a, b, c);}coord.push_back(0);sort(coord.begin(), coord.end());sort(abc.begin(), abc.end(), [](decltype(abc)::value_type p,decltype(abc)::value_type q) {int a, b, x, y;long long c, z;tie(a, b, c) = p;tie(x, y, z) = q;if (a < x) return true;if (a > x) return false;if (b > y) return true;return false;});constexpr long long inf = 1LL << 60;segment_tree<long long> sgt(coord,[](long long a, long long b){return max(a, b);},-inf);sgt.update(0, 0);for (auto const& p : abc) {int b; long long c;tie(ignore, b, c) = p;long long tmp = sgt.query(0, b) + c;if (sgt.at(b) < tmp) sgt.update(b, tmp);}cout << sgt.query(0, 1 << 30) << endl;return 0;}