結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

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

/**
* @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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0