Cod sursa(job #2216299)

Utilizator NOSCOPEPROKENDYMACHEAMACUMVREAU NOSCOPEPROKENDY Data 26 iunie 2018 12:05:29
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <deque>
#include <string.h>
 
using namespace std;
 
int n, k;
 
struct entry {
    int value;
    int index;
};
 
deque<entry> d;
int v[500025];
char s[4000005];
 
int main() {
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
 
    scanf("%d %d\n", &n, &k);
 
    int best = -0x3f3f3f3f;
    int bestOcc;
 
    gets(s);
 
    int nn = strlen(s);
    int i = 0;
    int semn;
    int nr = 0;
    int kk = 0;
    while (i<nn) {
        semn = 1;
        if (s[i] == '-') {
            semn = -1;
            ++i;
        }
        while (i<nn && s[i] >= '0' && s[i] <= '9') {
            nr = nr * 10 + s[i] - '0';
            ++i;
        }
        nr *= semn;
        v[kk] = nr;
        nr = 0;
        ++i;
        ++kk;
    }
 
    for (int i = 0; i < n; ++i) {
        int x = v[i];
         
        while (!d.empty() && d.back().value >= x) {
            d.pop_back();
        }
        if (!d.empty() && d.front().index <= i - k) {
            d.pop_front();
        }
        d.push_back({ x, i });
 
        if (i >= k - 1 && d.front().value > best) {
            best = d.front().value;
            bestOcc = i - k + 1;
        }
    }
 
    printf("%d %d %d", bestOcc + 1, bestOcc + k, best);
 
    return 0;
}