Submission #2755532
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template <typename T,typename E>
struct SegmentTree{
using F = function<T(T,T)>;
using G = function<T(T,E)>;
Int n;
F f;
G g;
T ti;
vector<T> dat;
SegmentTree(){};
SegmentTree(Int n_,F f,G g,T ti):
f(f),g(g),ti(ti){
init(n_);
}
void init(Int n_){
n=1;
while(n<n_) n*=2;
dat.assign(2*n-1,ti);
}
void build(Int n_, vector<T> v){
for(Int i=0;i<n_;i++) dat[i+n-1]=v[i];
for(Int i=n-2;i>=0;i--)
dat[i]=f(dat[i*2+1],dat[i*2+2]);
}
void update(Int k,E a){
k+=n-1;
dat[k]=g(dat[k],a);
while(k>0){
k=(k-1)/2;
dat[k]=f(dat[k*2+1],dat[k*2+2]);
}
}
inline 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++)-1]);
if(r&1) vr=f(dat[(--r)-1],vr);
}
return f(vl,vr);
}
Int find(Int a,Int b,function<bool(T)> &check,Int k,Int l,Int r){
if(!check(dat[k])||r<=a||b<=l) return -1;
if(k>=n-1) return k-(n-1);
Int m=(l+r)>>1;
Int vl=find(a,b,check,k*2+1,l,m);
if(~vl) return vl;
return find(a,b,check,k*2+2,m,r);
}
Int find(Int a,Int b,function<bool(T)> &check){
return find(a,b,check,0,0,n);
}
};
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;}
//INSERT ABOVE HERE
signed main(){
Int n;
cin>>n;
vector<Int> a(n);
for(Int i=0;i<n;i++) cin>>a[i];
auto f=[](Int a,Int b){return max(a,b);};
auto g=[](Int a,Int b){a++;return b;};
Int ans=0;
SegmentTree<Int, Int> seg(n,f,g,0);
for(Int i=0;i<n;i++){
Int k=seg.query(0,i-a[i])+1;
seg.update(i,k);
chmax(ans,k);
}
cout<<ans<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - リス |
User |
beet |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1890 Byte |
Status |
WA |
Exec Time |
142 ms |
Memory |
10752 KB |
Judge Result
Set Name |
sample |
all |
Score / Max Score |
0 / 0 |
0 / 1 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt, sample-03.txt |
all |
sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, sample-01.txt, sample-02.txt, sample-03.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
2 ms |
384 KB |
01-02.txt |
AC |
1 ms |
256 KB |
01-03.txt |
WA |
1 ms |
256 KB |
01-04.txt |
WA |
1 ms |
256 KB |
01-05.txt |
WA |
1 ms |
256 KB |
01-06.txt |
WA |
1 ms |
256 KB |
01-07.txt |
WA |
2 ms |
256 KB |
01-08.txt |
WA |
2 ms |
384 KB |
01-09.txt |
WA |
9 ms |
896 KB |
01-10.txt |
WA |
139 ms |
10752 KB |
01-11.txt |
WA |
140 ms |
10752 KB |
01-12.txt |
WA |
138 ms |
10752 KB |
01-13.txt |
WA |
136 ms |
10752 KB |
01-14.txt |
WA |
137 ms |
10752 KB |
01-15.txt |
WA |
140 ms |
10752 KB |
01-16.txt |
WA |
142 ms |
10752 KB |
01-17.txt |
AC |
102 ms |
10752 KB |
01-18.txt |
AC |
116 ms |
10752 KB |
sample-01.txt |
AC |
1 ms |
256 KB |
sample-02.txt |
AC |
1 ms |
256 KB |
sample-03.txt |
AC |
1 ms |
256 KB |