Cod sursa(job #253156)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 14:59:50
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.57 kb
   #include <stdio.h>  
   #include <algorithm>  
   #define mx 1 << 19  
    
   using namespace std;  
     
   char s[1 << 22];  
  pair <short, int> dq[mx];  
   short a[mx];  
   int n, k, stdq = 1, sfdq = 1, maxim, ts, tf;  
    
  int main()  
  {  
       freopen("secventa.in","r",stdin);  
       freopen("secventa.out","w",stdout);  
       scanf("%d %d\n", &n, &k);  
       fgets(s, 1 << 22, stdin);  
       int x = 0, sm = 1;  
       for (int id = 0, i = 0; i <= n; id++)  
       {  
           if (s[id] == '-')  
               sm = -1;  
           else if ('0' <= s[id] && s[id] <= '9')  
               x = x * 10 + s[id] - '0';  
           else  
           {  
               a[++i] = x * sm;  
              x = 0;  
               sm = 1;  
           }  
       }  
       dq[stdq].first = 30001;  
       maxim = -LONG_MAX;  
       for (int i = 1; i <= n; i++)  
       {  
           if (dq[stdq].second <= i - k)  
               stdq++;  
           int vl = min(a[i], dq[stdq].first);  
           if (vl > maxim && i >= k)  
           {  
              ts = i - k + 1;  
              tf = i;  
              maxim = vl;  
          }  
          dq[++sfdq].first = a[i];  
           dq[sfdq].second = i;  
           while (dq[sfdq].first < dq[sfdq - 1].first && sfdq > stdq)  
           {  
               swap(dq[sfdq], dq[sfdq - 1]);  
               sfdq--;  
           }  
       }  
       printf("%d %d %d", ts, tf, maxim);  
       fclose(stdin);  
       fclose(stdout);  
       return 0;  
   }