Cod sursa(job #1533846)

Utilizator mariusadamMarius Adam mariusadam Data 23 noiembrie 2015 02:10:08
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <deque>
#include <fstream>
#define pb push_back
#define mp make_pair
using namespace std;

struct elem{
    int val, ind;
} DE[500001];
int n, k, x, st = 0, sf = 0, sz = 0;

int main() {
    ifstream r("secventa.in");
    ofstream w("secventa.out");
    r >> n >> k;
    elem bmax;
    bmax.val = -(1 << 30);
    for (int i = 1; i <= n; i++) {
        r >> x;
        while (sf > st and x >= DE[sf].val)
            sf = sf - 1;
        if (sf - st < k) {
            sf++;
            DE[sf].val = x;
            DE[sf].ind = i;
        }
        if (i - DE[st].ind == k)
            st++;
        if (i >= k && DE[st].val) {
            bmax.val = DE[st].val;
            bmax.ind = i;
        }
    }
    w << bmax.ind - k + 1 << " " << bmax.ind << " " << bmax.val;
    r.close();
    w.close();
    return 0;
}