Cod sursa(job #1212945)

Utilizator MarronMarron Marron Data 26 iulie 2014 17:30:27
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

// <parsing>
FILE* f = fopen("secventa.in", "r");
const int maxb = 8192;
char buf[maxb];
int ptr = maxb;

inline int getInt()
{
    int mul = 1;
    while (buf[ptr] < '0' || '9' < buf[ptr]) {
        if (buf[ptr] == '-') {
            mul = -1;
        }
        if (++ptr >= maxb) {
            fread(buf, maxb, 1, f);
            ptr = 0;
        }
    }
    int nr = 0;
    while ('0' <= buf[ptr] && buf[ptr] <= '9') {
        nr = nr * 10 + buf[ptr] - '0';
        if (++ptr >= maxb) {
            fread(buf, maxb, 1, f);
            ptr = 0;
        }
    }
    return nr * mul;
}
// </parsing>
FILE* g = fopen("secventa.out", "w");

#define MAXN 500005
int n, k;
int a[MAXN];
deque<int> dq;
int solst, soldr, sol = -0x3f3f3f3f;

int main()
{
    n = getInt();
    k = getInt();
    for (int i = 1; i < k; i++) {
        a[i] = getInt();
        while (!dq.empty() && a[dq.back()] >= a[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }
    for (int i = k; i <= n; i++) {
        a[i] = getInt();
        while (!dq.empty() && a[dq.back()] >= a[i]) {
            dq.pop_back();
        }
        dq.push_back(i);

        if (dq.front() <= i - k) {
            dq.pop_front();
        }

        if (a[dq.front()] > sol) {
            sol = a[dq.front()];
            solst = i - k + 1;
            soldr = i;
        }
    }

    fprintf(g, "%d %d %d\n", solst, soldr, sol);

    return 0;
}