Cod sursa(job #2082448)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 6 decembrie 2017 11:02:28
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");

char str[10000006];
int N, K, j, u, dr, s = 1, MAX = -300001, st[500003], a[500003];
int main()
{
    f >> N >> K;
    f.get();
    f.getline(str, 10000006);
    for(int i = 1; i <= N; i++) {
        int semn = 1;
        if(str[j] == ' ') j++;
        if(str[j] == '-') semn = -1, j++;
        while(isdigit(str[j])) a[i] = a[i] * 10 + (str[j] - '0'), j++;
        a[i] *= semn;
    }
    for(int i = 1; i <= N; i++) {
        while(s <= dr && a[i] < a[st[dr]]) dr--;
        st[++dr] = i;
        if(st[s] <= i - K) s++;
        if(i >= K && a[st[s]] > MAX) MAX = a[st[s]], u = i;
    }
    g << u - K + 1 << " " << u << " " << MAX << "\n";
    return 0;
}