Cod sursa(job #1169894)

Utilizator ThomasFMI Suditu Thomas Thomas Data 12 aprilie 2014 12:18:37
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <cstdio>
#include <deque>
#define DIM 8192
using namespace std;
int n,k,x,maxim,p1,p2,A[500009];
char ax[DIM + 16];
int pz;
deque < int > dq;
 
inline void cit(int &x)
{
    x = 0;
    while((ax[pz] < '0' || ax[pz] > '9') && ax[pz] != '-')
    {
        if(++pz == DIM) fread(ax, 1, DIM, stdin), pz = 0;
    }
 
    int neg = 0;
    if(ax[pz] == '-')
    {
        neg = 1;
        if(++pz == DIM) fread(ax, 1, DIM, stdin), pz = 0;
    }
    while(ax[pz] >= '0' && ax[pz] <= '9')
    {
        x = x*10 + ax[pz]-'0';
        if(++pz == DIM) fread(ax, 1, DIM, stdin), pz = 0;
    }
    if(neg) x = -x;
}
 
int main()
{
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
 
    scanf("%d%d", &n,&k);
    for(int i=1; i<=n; i++) cit(A[i]);
    maxim = -30001;
    for(int i=1; i<=n; i++)
    {
        while(!dq.empty() && A[i] <= A[dq.back()]) dq.pop_back();
        dq.push_back(i);
        if(i-dq.front()+1 > k) dq.pop_front();
        if(i >= k && A[dq.front()] > maxim) maxim = A[dq.front()], p1 = i-k+1, p2 = i;
    }
    printf("%d %d %d\n", p1,p2,maxim);
    return 0;
}