Submission #134130

#	Time	Username	Problem	Language	Result	Execution time	Memory
134130		dragonslayerit	Global Warming (CEOI18_glo)	C++14	100 / 100	633 ms	24956 KiB

glo

#include <cstdio>
#include <algorithm>
#include <map>

const int INF=1e9+7;

int ts[200005];

int lis[400005];
int lisd[400005];

void update(int* ft,int i,int v){
  for(;i<=400004;i+=(i&-i)){
    ft[i]=std::max(ft[i],v);
  }
}

int query(int* ft,int i){
  int ac=0;
  for(;i>0;i-=(i&-i)){
    ac=std::max(ac,ft[i]);
  }
  return ac;
}

int main(){
  int N,X;
  scanf("%d %d",&N,&X);
  std::map<int,int> cps;
  for(int i=0;i<N;i++){
    scanf("%d",&ts[i]);
    cps[ts[i]];
    cps[ts[i]+X];
  }
  {
    int last=1;
    for(auto& it:cps){
      it.second=last++;
    }
  }
  for(int i=0;i<N;i++){
    int x=cps[ts[i]],y=cps[ts[i]+X];
    update(lisd,x,1+query(lisd,x-1));
    update(lisd,x,1+query(lis,y-1));
    update(lis,x,1+query(lis,x-1));
  }
  printf("%d\n",query(lisd,400004));
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&N,&X);
   ~~~~~^~~~~~~~~~~~~~~
glo.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&ts[i]);
     ~~~~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25