Cod sursa(job #2327903)

Utilizator gabiluciuLuciu Gabriel gabiluciu Data 25 ianuarie 2019 10:30:40
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.05 kb
/*
____    _____      ____   _____     _____   ____    _____   ____    _   _   ___   _____
|  _ \  | ____|    / ___| | ____|   |_   _| |  _ \  | ____| | __ )  | | | | |_ _| | ____|
| | | | |  _|     | |     |  _|       | |   | |_) | |  _|   |  _ \  | | | |  | |  |  _|
| |_| | | |___    | |___  | |___      | |   |  _ <  | |___  | |_) | | |_| |  | |  | |___
|____/  |_____|    \____| |_____|     |_|   |_| \_\ |_____| |____/   \___/  |___| |_____|
{1}
____       _      ____    ____    _____   ____    ___
|  _ \     / \    |  _ \  / ___|  | ____| |  _ \  |__ \
 | |_) |   / _ \   | |_) | \___ \  |  _|   | |_) |   / /
|  __/   / ___ \  |  _ <   ___) | | |___  |  _ <   |_|
|_|     /_/   \_\ |_| \_\ |____/  |_____| |_| \_\  (_)
{1}
{1}
{1}
_   _   _   _    __     __   ___    ___      _      __  __
| \ | | | | | |   \ \   / /  / _ \  |_ _|    / \    |  \/  |
|  \| | | | | |    \ \ / /  | | | |  | |    / _ \   | |\/| |
| |\  | | |_| |     \ V /   | |_| |  | |   / ___ \  | |  | |
|_| \_|  \___/       \_/     \___/  |___| /_/   \_\ |_|  |_|
{1}
____       _        _____   _   _   ____
/ ___|     / \      |  ___| | | | | |  _ \
 \___ \    / _ \     | |_    | | | | | |_) |
___) |  / ___ \    |  _|   | |_| | |  _ <   _   _   _
|____/  /_/   \_\   |_|      \___/  |_| \_\ (_) (_) (_)
{1}
{1}
{1}
_             _    ___     ___    _  __       __
        __| |   __ _    / |  / _ \   / _ \  (_)/ /    _  \ \
  / _` |  / _` |   | | | | | | | | | |   / /    (_)  | |
| (_| | | (_| |   | | | |_| | | |_| |  / /_     _   | |
\__,_|  \__,_|   |_|  \___/   \___/  /_/(_)   (_)  | |
/_/
{1}
{1}
*/

//#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <set>
#include <algorithm>
#include <bitset>
#include <time.h>
#include <tuple>
#include <fstream>
#include <iomanip>
#include <utility>

#pragma warning "da 100% din tine. :)"
#define nl '\n'
#define cnl cout << '\n';
#define pb(x) push_back(x)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define ll long long
#define ull unsigned ll
#ifdef INFOARENA
#define ProblemName "secventa"
#endif
#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "a.in"
#define OuFile "a.out"
#endif

//start copied part
class InParser {
private:

    FILE *fin;
    char *buff;
    int sp;
    char read_ch() {
        sp++;

        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }

        return buff[sp];
    }

public:

    InParser(const char *nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser &operator>>(int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');

        int sgn = 1;

        if (c == '-') {
            n = 0;
            sgn = -1;
        } else
            n = c - '0';

        while (isdigit(c = read_ch()))
            n = 10 * n + c - '0';

        n *= sgn;

        return *this;
    }
};
//end copied part
using namespace std;
InParser cin(InFile);
ofstream cout(OuFile);


template<class v, class type>
void print(v Vector, type nr) {
    for_each(all(Vector), [](type x) {
        cout << x << ' ';
    });
}

void nimic() {
    return;
}

deque<int> dq;
int arr[500001];
ll sum = 0;
int el;

int main() {
    freopen(InFile, "r", stdin);
    freopen(OuFile, "w", stdin);
    ios_base::sync_with_stdio(false);
    clock_t tStart = clock();
    int k, n, globalmin = -9999999;
    cin >> n >> k;
    int x = -1;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }
    for (int i = 1; i <= n; ++i) {
        while (!dq.empty() && arr[dq.back()] >= arr[i])
            dq.pop_back();
        dq.push_back(i);
        if (i - k == dq.front())
            dq.pop_front();
        if (i >= k && arr[dq.front()] > globalmin) {
            globalmin = arr[dq.front()];
            x = i;
        }
    }

    cout << x - k + 1 << ' ' << x << ' ';
    cout << globalmin;
    printf("\nTime taken: %.2fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
}