Cod sursa(job #2251543)

Utilizator LucaSeriSeritan Luca LucaSeri Data 1 octombrie 2018 18:27:23
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;

typedef pair< int, int > pii;
typedef pair< long long, long long > pll;
typedef long long ll;
typedef vector< int > vi;
typedef vector< ll > vll;
typedef vector< pii > vpii;
typedef vector< pll > vpll;
typedef long double ld;

const ll MOD = 1e9 + 7;
ll lgput(ll a, ll b, ll mod) {
    ll ret = 1;
    while( b ){
        if(b & 1) ret = (ret * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }

    return ret;
}

int binarySearch(vector< int > &v, int value) {
    int best = 0;
    for(int step = 29; step >= 0; --step) {
        if(best + (1<<step) < v.size() && v[best + (1<<step)] <= value) best += (1<<step);
    }

    return best;
}

inline ll inv(ll x, ll MOD) {
    return lgput(x, MOD - 2, MOD);
}

const int MAXN = 5e5 + 10;
int lft, rght;
pair< int, int > dq[MAXN];

int main() {
    //freopen("input", "r", stdin); freopen("output", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    cout << fixed;

    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    int l, r, ans = -1e9;
    int n, k;
    scanf("%d%d", &n, &k);

    for(int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        while(lft != rght  && dq[lft].first <= i-k) lft++;
        while(lft != rght && dq[rght].second > x) rght--;

        dq[++rght] = make_pair(i, x);
        if(i < k) continue;
        if(dq[lft].second > ans) {
            ans = dq[lft].second;
            r = i;
            l = i - k + 1;
        }
    }

    printf("%d %d %d\n", l, r, ans);
    return 0;
}