結果
問題 | No.1868 Teleporting Cyanmond |
ユーザー |
|
提出日時 | 2024-10-06 19:43:16 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 112 ms / 2,000 ms |
コード長 | 2,444 bytes |
コンパイル時間 | 1,325 ms |
コンパイル使用メモリ | 130,012 KB |
実行使用メモリ | 14,592 KB |
最終ジャッジ日時 | 2024-10-06 19:43:21 |
合計ジャッジ時間 | 4,301 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
#include<iostream>#include<string>#include<queue>#include<vector>#include<cassert>#include<random>#include<set>#include<map>#include<cassert>#include<unordered_map>#include<bitset>#include<numeric>#include<algorithm>using namespace std;typedef long long ll;const int inf=1<<30;const ll INF=1LL<<62;typedef pair<int,ll> P;typedef pair<int,P> PP;const ll MOD=998244353;int op(int x, int y){//(x,y)を比較する任意の演算子.今回はmaxとしたreturn min(x,y);}int e(){//initialize valuereturn inf;}template<class Type,Type (*op)(Type,Type),Type (*e)()> class segment_tree{public:std::vector<Type> dat;int n=1;segment_tree(int n_){while(n < n_){n*=2;}dat = std::vector<Type>(2*n-1,e());// 0,1,2,...,2*n-1,2*n-2}~segment_tree(){std::vector<Type>().swap(dat);}void set(int k,Type a){update(k,a);}void update(int k,Type a){k+=n-1;dat[k] = a;while(k>0){k = (k-1)/2;dat[k]=op(dat[2*k+1],dat[2*k+2]);}}//[a,b)Type query(int a,int b,int k,int l,int r){if(r<=a || b<=l) return e();if(a<=l && r<=b) return dat[k];else{Type vl = query(a,b,2*k+1,l,(l+r)/2);Type vr = query(a,b,2*k+2,(l+r)/2,r);return op(vl,vr);}}//[a,b)の範囲でのmaxType query(int a,int b){return query(a,b,0,0,n);}Type operator[](int index){return get(index);}Type get(int index){index += n-1;return dat[index];}void add(int index,Type val){update(index,op(get(index),val));}};int main(){int N;cin>>N;vector<int> R(N+1);map<int,vector<int>> mp;for(int i=1;i<N;i++){cin>>R[i];mp[R[i]].push_back(i);}segment_tree<int,op,e> seg(N+5);seg.add(1,0);for(int i=1;i<=N;i++){for(int c:mp[i]){//[c,i)の中でminint val=seg.query(c,i);seg.add(i,val+1);}}int ans=seg.query(N,N+1);cout<<ans<<endl;}