Cod sursa(job #253161)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 15:05:09
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.43 kb
   #include <cstdio>  
     
   #define Nmax 500015  
     
  int N, K;  
   int best_st, best_dr, best;  
   int sir[Nmax];  
   int D[Nmax];  
   char s[Nmax * 8], *buf;  
     
  int get()  
   {  
       int ret = 0, sgn = 1;  
       while (*buf == ' ') ++buf;  
       if (*buf == '-') sgn = -1, ++buf;  
       while ('0' <= *buf && *buf <= '9')  
       {  
          ret = ret * 10 + *buf - '0';  
           ++buf;  
       }  
   
       return ret * sgn;  
  }  
     
   void citire()  
   {  
       scanf("%d%d\n", &N, &K);  
       fgets(s, Nmax * 8, stdin);  
       buf = s;  
       for (int i = 1; i <= N; ++i)  
           sir[i] = get();  
   }  
     
   void solve()  
   {  
     int st = 1, dr = 0;  
     
      best = -30001;  
       for (int i = 1; i <= N; ++i)  
       {  
           while (st <= dr && sir[D[dr]] > sir[i]) --dr;  
          D[++dr] = i;  
          while (st <= dr && D[st] <= i - K) ++st;  
     
           if (i >= K && best < sir[D[st]])  
           {  
               best = sir[D[st]];  
              best_st = i - K + 1;  
              best_dr = i;  
           }  
      }  
    
       printf("%d %d %d\n", best_st, best_dr, best);  
   }  
     
   int main()  
   {  
       freopen("secventa.in", "r", stdin);  
       freopen("secventa.out", "w", stdout);  
     
       citire();  
       solve();  
     
       return 0;  
  }