Cod sursa(job #2734650)

Utilizator As932Stanciu Andreea As932 Data 1 aprilie 2021 10:39:07
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

const int nMax = 5e5 + 5;
const int lMax = 3e6 + 5e5 + 5;

int n, k, v[nMax], poz[nMax];
char s[lMax];

void read(){
    fin >> n >> k;
    fin.get();
    fin.getline(s, lMax - 5);

    int nr;
    for(int ind = 0, i = 1; i <= n; ind++, i++)
        if(s[ind] == '-'){
            for(nr = 0, ind++; s[ind] >= '0' && s[ind] <= '9'; ind++)
                nr = nr * 10 + (s[ind] - '0');
            v[i] = (-1) * nr;
        } else {
            for(nr = 0; s[ind] >= '0' && s[ind] <= '9'; ind++)
                nr = nr * 10 + (s[ind] - '0');
            v[i] = nr;
        }
}

void solve(){
    deque <int> q;
    q.push_back(1);

    for(int i = 2; i < k; i++){
        while(!q.empty() && v[i] <= v[q.back()])
            q.pop_back();
        q.push_back(i);
    }

    int mn, best = - (1 << 30), f = 0, s = 0;
    for(int i = k; i <= n; i++){
        while(!q.empty() && i - q.front() >= k)
            q.pop_front();

        mn = min(v[i], v[q.front()]);

        if(mn > best){
            best = mn;
            f = i - k + 1;
            s = i;
        }

        while(!q.empty() && v[i] <= v[q.back()])
            q.pop_back();
        q.push_back(i);
    }

    fout << f << " " << s << " " << best;
}

int main()
{
    read();
    solve();

    return 0;
}