結果
問題 | No.777 再帰的ケーキ |
ユーザー |
![]() |
提出日時 | 2019-03-27 15:03:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 301 ms / 2,000 ms |
コード長 | 2,128 bytes |
コンパイル時間 | 2,360 ms |
コンパイル使用メモリ | 220,488 KB |
最終ジャッジ日時 | 2025-01-07 00:32:34 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
ソースコード
#include<bits/stdc++.h>using namespace std;using Int = long long;template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}template <typename T>struct SegmentTree{using F = function<T(T,T)>;Int n;F f;T ti;vector<T> dat;SegmentTree(){};SegmentTree(F f,T ti):f(f),ti(ti){}void init(Int n_){n=1;while(n<n_) n<<=1;dat.assign(n<<1,ti);}void build(const vector<T> &v){Int n_=v.size();init(n_);for(Int i=0;i<n_;i++) dat[n+i]=v[i];for(Int i=n-1;i;i--)dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);}void set_val(Int k,T x){dat[k+=n]=x;while(k>>=1)dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);}T query(Int a,Int b){T vl=ti,vr=ti;for(Int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {if(l&1) vl=f(vl,dat[l++]);if(r&1) vr=f(dat[--r],vr);}return f(vl,vr);}};struct FastIO{FastIO(){cin.tie(0);ios::sync_with_stdio(0);}}fastio_beet;template<typename T>vector<T> compress(vector<T> v){sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());return v;}template<typename T>map<T, Int> dict(const vector<T> &v){map<T, Int> res;for(Int i=0;i<(Int)v.size();i++)res[v[i]]=i;return res;}//INSERT ABOVE HEREsigned main(){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];{using T = tuple<Int, Int, Int>;vector<T> vt;for(Int i=0;i<n;i++) vt.emplace_back(-a[i],b[i],c[i]);sort(vt.begin(),vt.end());for(Int i=0;i<n;i++) tie(a[i],b[i],c[i])=vt[i],a[i]=-a[i];}vector<Int> vs(b);vs.emplace_back(0);vs.emplace_back(1e9+100);vs=compress(vs);auto dc=dict(vs);auto f=[](Int a,Int b){return max(a,b);};SegmentTree<Int> seg(f,0);seg.build(vector<Int>(vs.size(),0));for(Int i=0;i<n;i++){Int k=dc[b[i]];Int v=seg.query(k+1,vs.size())+c[i];Int res=seg.query(k,k+1);if(res<v) seg.set_val(k,v);}cout<<seg.query(0,vs.size())<<endl;return 0;}