Cod sursa(job #45472)

Utilizator cos_minBondane Cosmin cos_min Data 1 aprilie 2007 15:45:47
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <stdio.h>
#include <fstream>
#include <deque>
using namespace std;

#define in "secventa.in"
#define out "secventa.out"
#define dim 500001

int N, K;
int A[dim];
int maxim = -1000001;
deque<int> pmin, pminp;
deque<int>::iterator it;
deque<int>::iterator it2;

int main()
{
    int start, finish;
    int j;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d%d", &N, &K);
    for ( int i = 1; i <= N; i++ )
        scanf("%d", &A[i]);
    
    pmin.push_back(A[1]);
    pminp.push_back(1);
    
    for ( int i = 2; i <= N; i++ )
    {
        if ( i <= K )
        {
             if ( A[i] < pmin[0] ) 
             {
                  pmin.clear();
                  pminp.clear();
                  pmin.push_back(A[i]);
                  pminp.push_back(i);
             }
             else
             {
                 j = pmin.size()-1;
                 while ( A[i] < pmin[j] ) pmin.pop_back(), pminp.pop_back(), j--; 
                 pmin.push_back(A[i]);
                 pminp.push_back(i);
             }
        }
        else
        {
            // caut daca am element de pe pozitia i-k-1;
            
            for ( it = pminp.begin(), it2 = pmin.begin(); it != pminp.end(); it++, it2++ )
                if ( *it == i-K ) 
                {
                     pminp.erase(it); 
                     pmin.erase(it2);
                     break;
                }
            
            if ( A[i] < pmin[0] ) 
            {
                  pmin.clear();
                  pminp.clear();
                  pmin.push_back(A[i]);
                  pminp.push_back(i);
            }
            else
            {
                 j = pmin.size()-1;
                 while ( A[i] < pmin[j] ) pmin.pop_back(), pminp.pop_back(), j--; 
                 pmin.push_back(A[i]);
                 pminp.push_back(i);
            }
        }
        
      /*  for ( j = 0; j < pmin.size(); j++ )
            printf("%d %d\n", pmin[j], pminp[j]);
        
        printf("\n");*/
        
        
        if ( maxim < pmin[0] ) 
        {
             if ( i <= K ) start = 1, finish = K, maxim = pmin[0];
             else maxim = pmin[0], start = i-K+1, finish = i;
        }
    }
    
    printf("%d %d %d", start, finish, maxim);
}