Cod sursa(job #435864)

Utilizator raduiris94Alexa Radu raduiris94 Data 7 aprilie 2010 22:08:16
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <stdio.h> 
#include <deque> 
using namespace std; 
#define infile "secventa.in" 
#define outfile "secventa.out" 
#define NMAX 500005 
FILE *fin,*fout; 
int n,k; 
int x[NMAX]; 
int baza=-35000,start=-1; 
char sir[NMAX*10]; 
deque <int> coada;  
void citire()   
{  
int j=0,semn;   
fin=fopen(infile,"r");   
fscanf(fin,"%d %d\n",&n,&k); 
fgets(sir,sizeof(sir),fin);    
for(int i=0;i<n;i++) 
{ 
semn=0; 
x[i]=0; 
while(sir[j]!='-' && (sir[j]<'0' || sir[j]>'9')) 
j++; 
if(sir[j]=='-') 
{ 
semn=1;          
j++;       
}        
while(sir[j]>='0' && sir[j]<='9')            
{             
x[i]=x[i]*10+(sir[j]-'0');              
j++;            
}        
if(semn)         
x[i]=-x[i];      
}   
fclose(fin);  
}  
void scriere()   
{   
fout=fopen(outfile,"w");  
fprintf(fout,"%d %d %d\n",start+1,start+k,baza); 
fclose(fout);  
} 
void solve() 
{   
int i;   
for(i=0;i<k;i++)     
{   
while(!coada.empty() && x[coada.back()]>=x[i])           
coada.pop_back();      
coada.push_back(i);      
}  
baza=x[coada.front()]; 
start=0;    
for(i=k;i<n;i++)     
{        
if(coada.front()==i-k)         
coada.pop_front();      
while(!coada.empty() && x[coada.back()]>=x[i])            
coada.pop_back();     
coada.push_back(i);       
if(baza<x[coada.front()])        
{         
baza=x[coada.front()];         
start=i-k+1;         
}    
}   
} 
int main() 
{ 
citire(); 
solve(); 
scriere(); 
return 0; 
}