제출 #1120033

#제출 시각아이디문제언어결과실행 시간메모리
1120033nikolashamiGlobal Warming (CEOI18_glo)C++17
45 / 100
1428 ms262144 KiB
#include <bits/stdc++.h> using namespace std; const int N=2e5+4; int a[N],preflis[N],suflds[N],n,x; vector<int>dp; int nadjipederaalnaopacke(int x){ if(dp.empty()||x<dp.back())return dp.size(); int l=0,r=dp.size(); while(l<r){ int m=(l+r)/2; if(dp[m]>x) l=m+1; else r=m; } return l; } const int N2=31*2e5; int lc[N2],rc[N2],st[N2],ret,m,c,id=1; void make(int&node){ if(!node)node=++id; } map<int,int>sigma; void qry(int l,int r,int node=1,int tl=1,int tr=2e9){ if(tl>=l&&tr<=r){ ret=max(ret,sigma[st[node]]); return; } make(lc[node]); make(rc[node]); int mid=(tl+tr)/2; if(mid>=l)qry(l,r,lc[node],tl,mid); if(mid+1<=r)qry(l,r,rc[node],mid+1,tr); } void upd(int id,int val,int node=1,int tl=1,int tr=2e9){ if(tl==tr){ st[node]=val; return; } make(lc[node]); make(rc[node]); int mid=(tl+tr)/2; if(mid>=id)upd(id,val,lc[node],tl,mid); if(mid+1<=id)upd(id,val,rc[node],mid+1,tr); if(sigma[st[lc[node]]]>sigma[st[rc[node]]])st[node]=st[lc[node]]; else st[node]=st[rc[node]]; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>x; for(int i=0;i<n;++i) cin>>a[i]; for(int i=0;i<n;++i){ int id=lower_bound(dp.begin(),dp.end(),a[i])-dp.begin(); int sigma=-1; if(dp.empty()||a[i]>dp.back()){ dp.push_back(a[i]); sigma=(dp.empty()?0:dp.size()-1); } else dp[id]=a[i]; if(sigma==-1)sigma=id; preflis[i]=(sigma+1); } dp.clear(); for(int i=n-1;i>=0;--i){ int id=nadjipederaalnaopacke(a[i]); if(id==dp.size())dp.push_back(a[i]); else dp[id]=a[i]; suflds[i]=(id+1); } int ans=dp.size(); for(int i=n-1;i>=0;--i){ ret=0; qry(a[i]+1,2e9); ans=max(ans,ret+preflis[i]); sigma[a[i]+x]=max(sigma[a[i]+x],suflds[i]); upd(a[i]+x,a[i]+x); } cout<<ans; }

컴파일 시 표준 에러 (stderr) 메시지

glo.cpp: In function 'int main()':
glo.cpp:79:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         if(id==dp.size())dp.push_back(a[i]);
      |            ~~^~~~~~~~~~~
#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...