Submission #1094104

#TimeUsernameProblemLanguageResultExecution timeMemory
1094104alexander707070Global Warming (CEOI18_glo)C++14
58 / 100
1056 ms179140 KiB
#include<bits/stdc++.h> #define MAXN 200007 using namespace std; const long long inf=1e9; struct ST{ struct node{ int l,r,val; }; node tree[100*MAXN]; int num; void init(){ num=1; tree[num]={0,0,0}; } void addnode(){ num++; tree[num]={0,0,0}; } void check(int v){ if(tree[v].l==0){ addnode(); tree[v].l=num; } if(tree[v].r==0){ addnode(); tree[v].r=num; } } void update(int v,long long l,long long r,long long pos,int val){ if(l==r){ tree[v].val=max(tree[v].val,val); }else{ long long tt=(l+r)/2; check(v); if(pos<=tt)update(tree[v].l,l,tt,pos,val); else update(tree[v].r,tt+1,r,pos,val); tree[v].val=max(tree[tree[v].l].val,tree[tree[v].r].val); } } int getmax(int v,long long l,long long r,long long ll,long long rr){ if(ll>rr or v==0)return 0; if(l==ll and r==rr){ return tree[v].val; }else{ long long tt=(l+r)/2; return max( getmax(tree[v].l,l,tt,ll,min(tt,rr)) , getmax(tree[v].r,tt+1,r,max(tt+1,ll),rr) ); } } }seg[3]; int n,a[MAXN],ans,x; int dp[MAXN][3]; int solve(int d){ seg[0].init(); seg[1].init(); seg[2].init(); int res=0; for(int i=1;i<=n;i++){ dp[i][0]=seg[0].getmax(1,0,3*inf,0,a[i]-1)+1; dp[i][1]=max(seg[1].getmax(1,0,3*inf,0,a[i]-1)+1 , seg[0].getmax(1,0,3*inf,0,a[i]+d-1)+1); dp[i][2]=max(seg[2].getmax(1,0,3*inf,0,a[i]-1)+1 , seg[1].getmax(1,0,3*inf,0,a[i]-d-1)+1); seg[0].update(1,0,3*inf,a[i],dp[i][0]); seg[1].update(1,0,3*inf,a[i],dp[i][1]); seg[2].update(1,0,3*inf,a[i],dp[i][2]); res=max(res,max(dp[i][0],max(dp[i][1],dp[i][2]))); } return res; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>x; for(int i=1;i<=n;i++){ cin>>a[i]; a[i]+=inf+1; } cout<<max(solve(-x),solve(x))<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...