Cod sursa(job #2266601)

Utilizator cristii2000cristiiPanaite Cristian cristii2000cristii Data 22 octombrie 2018 19:56:00
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <deque>


using namespace std;

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

struct el{
    int indice, nr;
};

int n, k, curr;
deque <el> deq;
char s[3000100];

void read(int &x) {

    x = 0;

    int sign = 1;

    if(s[curr] == '-') {

        sign = -1;

        curr ++;

    }

    while('0' <= s[curr] && s[curr] <= '9') {

        x = x * 10 + (s[curr] - '0');

        curr ++;

    }

    curr ++;

    x *= sign;

}

int main() {

    ios_base::sync_with_stdio(false);
    in.getline(s, 3000100);
    read(n);
    read(k);
    in.getline(s, 3000100);
    curr = 0;
    el x;
    int valx;
    read(valx);
    x.nr = valx;
    x.indice = 1;
    deq.push_back(x);

    for (int i = 2; i < k; i++) {
        read(valx);
        x.nr = valx;
        x.indice = i;

        while (!deq.empty() && x.nr < deq.back().nr)
            deq.pop_back();
        deq.push_back(x);

    }
    el maxi;
    maxi.nr = -30005;
/*    deq.pop_front();*/

    for (int i = k; i <= n; i++) {
        read(valx);
        x.nr = valx;
        x.indice = i;

        while (!deq.empty() && x.nr < deq.back().nr) {
            deq.pop_back();
        }
        deq.push_back(x);
        if (deq.front().nr > maxi.nr) {
            maxi.nr = deq.front().nr;
            maxi.indice = i;
        }

        if (deq.back().indice - deq.front().indice == k - 1)
            deq.pop_front();
    }
        out << maxi.indice - k + 1 << " " << maxi.indice << " " << maxi.nr;

        return 0;
    }