結果
問題 | No.777 再帰的ケーキ |
ユーザー |
![]() |
提出日時 | 2020-06-12 18:45:34 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 694 ms / 2,000 ms |
コード長 | 3,411 bytes |
コンパイル時間 | 1,867 ms |
コンパイル使用メモリ | 183,196 KB |
実行使用メモリ | 18,960 KB |
最終ジャッジ日時 | 2024-06-24 04:05:34 |
合計ジャッジ時間 | 7,981 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
ソースコード
/*** @FileName a.cpp* @Author kanpurin* @Created 2020.06.12 18:45:29**/#include "bits/stdc++.h"using namespace std;typedef long long ll;template < class Monoid >struct SegmentTree {private:using Func = std::function< Monoid(Monoid, Monoid) >;Func F;Monoid UNITY;int n;std::vector< Monoid > node;public:SegmentTree() {}SegmentTree(int m, const Monoid &val, const Func f, const Monoid &unity) {F = f;UNITY = unity;n = 1;while (n < m) n <<= 1;node.resize(n * 2 - 1, UNITY);if (val != UNITY) {for (int i = 0; i < m; i++) node[i] = val;build();}}SegmentTree(const std::vector< Monoid > &v, const Func f, const Monoid &unity) {F = f;UNITY = unity;int sz = v.size();n = 1;while (n < sz) n <<= 1;node.resize(n * 2 - 1, UNITY);for (int i = 0; i < sz; i++) node[i + n - 1] = v[i];build();}void set(int k, const Monoid &x) {node[n + k - 1] = x;}void build() {for (int i = n - 2; i >= 0; i--) node[i] = F(node[2 * i + 1], node[2 * i + 2]);}void update_query(int x, const Monoid &val) {if (x >= n || x < 0) return;x += n - 1;node[x] = val;while (x > 0) {x = (x - 1) >> 1;node[x] = F(node[2 * x + 1], node[2 * x + 2]);}}/*Monoid query(int a, int b, int k = 0, int l = 0, int r = -1) {if (r < 0) r = n;if (r <= a || b <= l) return UNITY;if (a <= l && r <= b) return node[k];Monoid vl = query(a, b, 2 * k + 1, l, (r - l) / 2 + l);Monoid vr = query(a, b, 2 * k + 2, (r - l) / 2 + l, r);return F(vl, vr);}*/Monoid get_query(int a, int b) {Monoid L = UNITY, R = UNITY;if (a < 0) a = 0;if (b < 0) return UNITY;if (a >= n) return UNITY;if (b >= n) b = n;for (a += n, b += n; a < b; a >>= 1, b >>= 1) {if (a & 1) L = F(L, node[a++ - 1]);if (b & 1) R = F(node[--b - 1], R);}return F(L, R);}Monoid operator[](int x) const {return node[n + x - 1];}int size() {return n;}void print() {for (int i = 0; i < n; i++) {std::cout << i << "\t: " << node[n + i - 1] << std::endl;}}};int main() {int n;cin >> n;vector<tuple<int,int,int>> a(n);map<int,int> mp;for (int i = 0; i < n; i++) {int x,y,z;cin >> x >> y >> z;a[i] = make_tuple(x,y,z);mp[y] = 0;}int t = 0;for(auto p : mp) {mp[p.first] = t++;}typedef tuple<int,int,int> P;sort(a.begin(), a.end(), [](P a, P b) {if (get<0>(a) != get<0>(b)) return a < b;if (get<1>(a) != get<1>(b)) return a > b;return a > b;});SegmentTree<ll> seg(t,0,[](ll a,ll b){return max(a,b);},0);ll ans = 0;for (int i = 0; i < n; i++) {if (i > 0 && get<0>(a[i]) == get<0>(a[i-1]) && get<1>(a[i]) == get<1>(a[i-1])) continue;seg.update_query(mp[get<1>(a[i])],max(seg[mp[get<1>(a[i])]],seg.get_query(0,mp[get<1>(a[i])]) + get<2>(a[i])));ans = max(ans,seg[mp[get<1>(a[i])]]);}cout << ans << endl;return 0;}