Cod sursa(job #2850300)

Utilizator alextheseal1240Alex Vladu alextheseal1240 Data 16 februarie 2022 16:28:59
Problema Secventa Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#define inf 0x3f3f3f3f
#include <fstream>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int n, k;
int v[500001], a[2000001];
void read()
{
    fin >> n >> k;
    for(int i=1; i<=n; i++)
        fin >> v[i];
}
void build(int st, int dr, int nod)
{
    if(st==dr)
    {
        a[nod]=v[st];
        return;
    }
    int mid=(st+dr)>>1;
    build(st, mid, nod<<1), build(mid+1, dr, nod<<1|1);
    a[nod]=min(a[nod<<1], a[nod<<1|1]);
}
int quiz(int st, int dr, int x, int y, int nod)
{
    if(dr<x || st>y)
        return inf;
    if(x<=st && dr<=y)
        return a[nod];
    int mid=(st+dr)>>1;
    return min(quiz(st, mid, x, y, nod<<1), quiz(mid+1, dr, x, y, nod<<1|1));
}
void solve()
{
    int st=0, dr=0, maxi=-inf;
    for(int i=k; i<=n; i++)
    {
        int val=quiz(1, n, i-k+1, i, 1);
        if(maxi<val)
            maxi=val, st=i-k+1, dr=i;
    }
    fout << st << ' ' << dr << ' ' << maxi;
}
int main()
{
    read();
    build(1, n, 1);
    solve();
    return 0;
}