Cod sursa(job #857193)

Utilizator stoicatheoFlirk Navok stoicatheo Data 17 ianuarie 2013 16:04:54
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
 
ifstream fin("secventa.in");
ofstream fout("secventa.out");
 
 
#define NMAX 500003
 
int a[NMAX];
int N; int K;
deque <int> q;
int last , baza = 0;
char parse[NMAX *9], *p;
 
int getNumber() {
    int sgn = 1, x = 0;
 
    if(*p == ' ') ++p;
    if(*p == '-'){ sgn = -1 ; ++p;}
    while(!(*p >= '0' && *p <= '9')) ++p;
 
    while( *p >= '0' && *p <= '9') {x = x * 10 + *p - '0'; ++p;}
    x *= sgn;
    return x;
 
}
 
void Read () {
 
    fin >> N >>K;
    fin.getline(parse, NMAX * 9, '\0');
    p = parse;
    for(int i = 1; i <= N; i++)
        a[i] = getNumber ();
}
 
void Solve() {
 
    for(int i = 1; i <= K; i++){
        while(!q.empty() && a[i] <= a[q.back()]) q.pop_back();
        q.push_back(i);
    }
 
    baza = a[q.front()];
    last = K ;
 
    for(int i = K + 1 ; i <= N; i++){
        if(q.front() == i - K) q.pop_front();
 
        while(!q.empty() && a[i] <= a[q.back()]) q.pop_back();
        q.push_back(i);
 
        if(a[q.front()] > baza){
            baza = a[q.front()];
            last = i;
        }
    }
 
}
 
 
void Print(){
 
    fout << last - K + 1<<" "<<last << " "<< baza<<'\n';
}
 
 
int main() {
 
    Read();
 
    Solve();
 
    Print();
 
    return 0;
}