Cod sursa(job #2327891)

Utilizator gabiluciuLuciu Gabriel gabiluciu Data 25 ianuarie 2019 10:05:43
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
/*
ID: gabriel100
LANG: C++
TASK: milk2
*/

//#include <iostream>
#include <cstdio>
#include <algorithm>
//#include <time.h>
#include <queue>
#include <cmath>
#include <stack>
#include <fstream>
#include <bitset>
#include <set>

#define nl '\n'
#define all(v) v.begin(),v.end()
#define eb(x) emplace_back(x)
#define ull unsigned long long
#define LocalName "data"
#define ProblemName "secventa"
#ifdef INFOARENA
#define Filename ProblemName
#else
#define Filename LocalName
#endif
#define Input Filename".in"
#define Output Filename".out"
#define str(sir) #sir
#define N 500000
using namespace std;

ifstream cin(Input);
ofstream cout(Output);

template<class a, class type>
void print(a v, type t) {
    for_each(all(v), [](type x) { cout << x.first << ' '; });
    cout << nl;
}

int k, v[N + 3], n, currentMax, st, dr;

deque<pair<int, int> > d; // numar si pozitie
int main() {
    ios_base::sync_with_stdio(false);
//    clock_t tStart = clock();
    cin >> n >> k;
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        while (!d.empty() && i - d.front().second >= k) d.pop_front();
        cin >> v[i];
        if (d.empty()) {
            d.push_front({v[i], i});
        } else if (v[i] <= d.front().first) {
            d.pop_front();
            d.push_front({v[i], i});
        } else {
            while (!d.empty() && v[i] <= d.back().first)
                d.pop_back();
            d.push_back({v[i], i});
        }
        if (i >= k - 1) {
            if (d.front().first > currentMax) {
                currentMax = d.front().first;
                st = i - k + 1;
                dr = i;
            }
        }

    }
    cout << st+1 << ' ' << dr+1 << ' ' << currentMax << nl;

//    printf("\nTime taken: %.2fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
}