Cod sursa(job #911513)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 11 martie 2013 19:08:28
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <fstream>
#include <cstdio>
#include <deque>
using namespace std;
#define mp make_pair
#define pb push_back
#define popb pop_back
#define popf pop_front
 
#define pii pair<int, int>
#define val first
#define id second
 
// Constante
const int oo = (1<<30)-1;
const int parseSZ = (int)35e5+5;
 
// Variabile
ifstream in("secventa.in");
ofstream out("secventa.out");
 
char parseSTR[parseSZ], *parse=parseSTR;
 
int num, len;
 
deque<pii> values;
pii maxVal = mp(-oo, -oo);
 
// Main
int main()
{
    in >> num >> len;
    in.get();
    in.getline(parse, parseSZ);
    for(int i=1 ; i<len ; ++i)
    {
        int readVal = 0;
        bool sign = true;
        if(*parse == '-')
            sign = false, ++parse;
        while(*parse != ' ')
            readVal = readVal*10 + (*parse++)-'0';
        ++parse;
        if(!sign)
            readVal = -readVal;
         
        while(!values.empty() && readVal < values.back().val)
            values.popb();
        values.pb(mp(readVal, i));
    }
     
    for(int i=len ; i<=num ; ++i)
    {
        int readVal = 0;
        bool sign = true;
        if(*parse == '-')
            sign = false, ++parse;
        while(*parse != ' ')
            readVal = readVal*10 + (*parse++)-'0';
        ++parse;
        if(!sign)
            readVal = -readVal;
         
        while(!values.empty() && readVal < values.back().val)
            values.popb();
        values.pb(mp(readVal, i));
         
        if(i - values.front().id == len)
            values.popf();
         
        if(maxVal.val < values.front().val)
        {
            maxVal.val = values.front().val;
            maxVal.id = i;
        }
    }
     
    out << maxVal.id-len+1 << ' ' << maxVal.id << ' ' << maxVal.val << '\n';
     
     
    in.close();
    out.close();
    return 0;
}