Cod sursa(job #45475)

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

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

char linie[7*dim+dim];
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;
    FILE *fin = fopen(in,"r");
    freopen(out,"w",stdout);
    
    fscanf(fin, "%d%d\n", &N, &K);
    
    fgets(linie,7*dim+dim-1,fin);
    
    int minus=1;
    int aux=0;
    j=0;
    int t=0;
    
    while ( j < strlen(linie) )
    {
        if ( linie[j] >= '0' && linie[j] <= '9' )
        {
            aux *= 10;
            aux += (int)linie[j]-48;
        }    
        else if ( linie[j] == '-' ) minus = -1;
        else if ( linie[j] == ' ' || linie[j] == '\n' )
        {
            t+=1;
            A[t] = minus*aux;
            minus = 1;
            aux = 0;
        } 
        j++;   
    }    
    
    
    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] && i >= K ) 
        {
             start = i-K+1, finish = i, maxim = pmin[0];
        }
    }
    
    printf("%d %d %d", start, finish, maxim);
}