UVa 957 - Popes



#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <bitset>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef std::vector<int> vi;
typedef std::vector<pair<int, int> > vii;
#define FOR(l) for(vi::iterator it=l.begin();it!=l.end();it++)
#define FOR_L(l, s, e) for(vi::iterator it=l.begin()+s;it!=l.end()-e;it++)
inline int input(){
 int t=0;
 char c;
 c=getchar ();
 while(c<'0' || c>'9')
  c=getchar ();
 while(c>='0' && c<='9')
 {
  t=(t<<3)+(t<<1)+c-'0';
  c=getchar ();
 }
 return(t);
}

//----------Main source code -----------------//
int p[100000 +1], P;
int main() {
 int y, i, first, last, mid, end, ans=0, af, al;
 while(scanf("%d",&y)!=EOF){
  P=input();
  ans=0;//reset ans

  for(i=0;i<P;i++)
   p[i]=input();
  for(i=0;i<P;i++){
   //search upper_bound by binary search
   first = i+1;
   last = P-1;
   end = p[i]+y-1;
   while(last>first){
    mid = (first+last)/2;
    if(p[mid]>end) last=mid;
    else first = mid+1;
   }
   if(ans<last-i){
    ans=last-i;
    af=p[i];
    al=p[last-1];
   }
  }
  printf("%d %d %d\n", ans, af, al);
 }
 return 0;
}
Runtime:0.029
Ideone: http://ideone.com/iv22aU

Comments

Popular Posts