Cod sursa(job #2146845)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 28 februarie 2018 11:36:33
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>
#include <cstring>
#include <deque>
using namespace std;
deque <int> d;
const int NMAX = 500005;
int v[NMAX];
char s[1000];

int main() {
  int n, k;
  freopen("secventa.in", "r", stdin);
  freopen("secventa.out", "w", stdout);
  scanf("%d%d\n", &n, &k);
  for(int i = 1; i <= n; ++i) {
    scanf("%s", s);
    int ss = 1;
    int j = 0;
    if(s[j] == '-') {
      ss = -1;
      ++j;
    }
    while(s[j] >= '0' && s[j] <= '9') {
      v[i] = v[i] * 10 + s[j] - '0';
      ++j;
    }
    v[i] *= ss;
  }
  for(int i = 1; i < k; ++i) {
    while(!d.empty() && v[d.back()] > v[i]) {
      d.pop_back();
    }
    d.push_back(i);
  }
  int pozi = 0, pozs = 0;
  int sol = -0x7fffffff;
  for(int i = k; i <= n; ++i) {
    while(!d.empty() && v[d.back()] > v[i]) {
      d.pop_back();
    }
    while(!d.empty() && d.front() <= i - k) {
      d.pop_front();
    }
    d.push_back(i);
    if(sol < v[d.front()] && i >= k) {
      sol = v[d.front()];
      pozs = i;
      pozi = i - k + 1;
    }
  }
  printf("%d %d %d\n", pozi, pozs, sol);
  return 0;
}