Submission #1094077

#TimeUsernameProblemLanguageResultExecution timeMemory
1094077alexander707070Global Warming (CEOI18_glo)C++14
58 / 100
2053 ms179656 KiB
#include<bits/stdc++.h> #define MAXN 200007 using namespace std; const int inf=1e9; struct ST{ struct node{ int l,r,val; }; node tree[30*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,int 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,2*inf,0,a[i]-1)+1; dp[i][1]=max(seg[1].getmax(1,0,2*inf,0,a[i]-1)+1 , seg[0].getmax(1,0,2*inf,0,a[i]+d-1)+1); dp[i][2]=max(seg[2].getmax(1,0,2*inf,0,a[i]-1)+1 , seg[1].getmax(1,0,2*inf,0,a[i]-d-1)+1); seg[0].update(1,0,2*inf,a[i],dp[i][0]); seg[1].update(1,0,2*inf,a[i],dp[i][1]); seg[2].update(1,0,2*inf,a[i],dp[i][2]); res=max(res,max(dp[i][0],max(dp[i][1],dp[i][2]))); } return res; } int sol[2000007],pos; 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]; } if(n<=1000){ vector<int> w={0}; for(int i=1;i<=n;i++){ for(int f=i+1;f<=n;f++){ if(a[i]-a[f]+1>=-x and a[i]-a[f]+1<=x){ w.push_back(a[i]-a[f]+1); } if(a[i]-a[f]-1>=-x and a[i]-a[f]-1<=x){ w.push_back(a[i]-a[f]-1); } } } sort(w.begin(),w.end()); for(int i=0;i<w.size();i+=max(1,int(w.size())/1000)){ sol[i]=solve(w[i]); if(sol[i]>ans){ ans=sol[i]; pos=i; } } for(int i=max(0,pos-500);i<=min(int(w.size())-1,pos+500);i++){ ans=max(ans,solve(w[i])); } cout<<ans<<"\n"; return 0; } long long l=-x,r=x,lt,rt; while(l+20<r){ lt=l+(r-l+1)/3; rt=r-(r-l+1)/3; int ls=solve(lt); int rs=solve(rt); if(ls>rs)l=lt; else if(rs>ls)r=rt; else{ break; } } for(int d=l;d<=r;d++){ ans=max(ans,solve(d)); } cout<<ans<<"\n"; return 0; }

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:115:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |   for(int i=0;i<w.size();i+=max(1,int(w.size())/1000)){
      |               ~^~~~~~~~~
#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...