제출 #223092

#제출 시각아이디문제언어결과실행 시간메모리
223092MKopchevGlobal Warming (CEOI18_glo)C++14
100 / 100
371 ms7892 KiB
#include<bits/stdc++.h> using namespace std; const int nmax=2e5+42; int n,x,inp[nmax]; int tree[4*nmax]; void update(int node,int l,int r,int pos,int val) { if(l==r) { tree[node]=val; return; } int av=(l+r)/2; if(pos<=av)update(node*2,l,av,pos,val); else update(node*2+1,av+1,r,pos,val); tree[node]=max(tree[node*2],tree[node*2+1]); } int query(int node,int l,int r,int lq,int rq) { if(l==lq&&r==rq)return tree[node]; int av=(l+r)/2,ret=0; if(lq<=av)ret=max(ret,query(node*2,l,av,lq,min(av,rq))); if(av<rq)ret=max(ret,query(node*2+1,av+1,r,max(av+1,lq),rq)); return ret; } int sorted_inp[nmax]; int longest_to_end[nmax]; int main() { scanf("%i%i",&n,&x); for(int i=1;i<=n;i++) { scanf("%i",&inp[i]); sorted_inp[i]=inp[i]; } sort(sorted_inp+1,sorted_inp+n+1); int output=0; for(int i=n;i>=1;i--) { int pos_up=upper_bound(sorted_inp+1,sorted_inp+n+1,inp[i])-sorted_inp; int pos_low=lower_bound(sorted_inp+1,sorted_inp+n+1,inp[i])-sorted_inp; if(pos_up<=n)longest_to_end[i]=query(1,1,n,pos_up,n); longest_to_end[i]++; output=max(output,longest_to_end[i]); update(1,1,n,pos_low,longest_to_end[i]); //cout<<i<<" -> "<<longest_to_end[i]<<endl; } for(int i=0;i<4*nmax;i++)tree[i]=0; for(int i=1;i<=n;i++) { //try to add int pos_add=lower_bound(sorted_inp+1,sorted_inp+n+1,inp[i]+x)-sorted_inp; pos_add--; if(pos_add) { output=max(output,query(1,1,n,1,pos_add)+longest_to_end[i]); //cout<<i<<" -> "<<query(1,1,n,1,pos_add)<<" "<<longest_to_end[i]<<endl; } int pos=lower_bound(sorted_inp+1,sorted_inp+n+1,inp[i])-sorted_inp; pos--; int current=0; if(pos)current=query(1,1,n,1,pos); current++; pos++; update(1,1,n,pos,current); } printf("%i\n",output); return 0; }

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

glo.cpp: In function 'int main()':
glo.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&x);
     ~~~~~^~~~~~~~~~~~~~
glo.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&inp[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...