結果

問題 No.777 再帰的ケーキ
ユーザー toshiki_full
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0