Cod sursa(job #154574)

Utilizator StTwisterKerekes Felix StTwister Data 11 martie 2008 12:06:30
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <cstdio>
#include <vector>
#include <set>
#include <deque>

using namespace std;

typedef long long LL;
typedef vector<int> vi;
typedef vector< vi > vii;
typedef vector<string> vs;
typedef vector<double> vd;
typedef pair<int, int> ii;
#define PB push_back
#define SZ(v) v.size()
#define ALL(v) (v).begin(), (v).end()
#define FORIT(i,c) for (typeof((c).end()) i=(c).begin(); i!=(c).end(); ++i)
#define FOR(i,n) for (int i = 0; i<(n); ++i)
#define FORE(i,n) for (int i = 0; i<=(n); ++i)
#define FORI(i,n1,n2) for (int i = n1; i<(n2); ++i)
#define FORIE(i,n1,n2) for (int i = n1; i<=(n2); ++i)
#define FORV(i,v) for (unsigned int i = 0; i<SZ(v); ++i)

#define INF 0x3f3f3f3f
#define EPS 1e-9

#define NMAX 500001

set<int> S;
int N,K;
int A[NMAX];
int Q[NMAX], pos[NMAX];
int k1,k2;

inline void push(int x, int p)
{
    while (k2>0 && Q[k2-1] >= x) --k2;
    Q[++k2] = x;
    pos[k2] = p;
}

int main()
{
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);

    scanf("%d %d", &N, &K);

    FOR(i,N)
        scanf("%d", &A[i]);
        //cin >> A[i];

    int bestpos, best;

    deque<int> Q;

    FOR(i,K)
    {
        while (!Q.empty() && A[Q.back()] >= A[i])
            Q.pop_back();
        Q.push_back(i);
    }

    best = A[Q.front()];
    bestpos = 0;

    FORI(i, K, N)
    {
        if (Q.front() == i-K)
            Q.pop_front();

        while (!Q.empty() && A[Q.back()] >= A[i])
            Q.pop_back();
        Q.push_back(i);

        if (best < A[Q.front()])
        {
            best = A[Q.front()];
            bestpos = i-K+1;
        }
    }

    //cout << bestpos+1 << " " << bestpos+K << " " << best;
    printf("%d %d %d", bestpos+1, bestpos+K, best);

    return 0;
}