Cod sursa(job #2231339)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 13 august 2018 21:15:48
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>

using namespace std;

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

const int NMAX = 500001;
int deq[NMAX], v[NMAX], curr;
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() {
    int n, k;
    cin.getline(s, 3000100);
    read(n);
    read(k);

    cin.getline(s, 3000100);
    curr = 0;
    for(int i = 1; i <= n; i ++)
        read(v[i]);

    int st = 1, dr = 1;
    deq[1] = 1;
    int sol = -30005, rsol = 1, lsol = 1;
    for(int i = 2; i <= n; i ++) {
        while(st <= dr && v[i] < v[deq[dr]])
            dr --;
        deq[++dr] = i;
        if(k <= i && sol < v[deq[st]]) {
            sol = v[deq[st]];
            rsol = i;
        }
        if(deq[dr] - deq[st] == k-1)
            st ++;
    }
    cout << rsol - k + 1 << " " << rsol << " " << sol;
    return 0;
}