Cod sursa(job #2092034)

Utilizator ajeccAjechiloae Eugen ajecc Data 20 decembrie 2017 20:23:32
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.37 kb
#include <bits/stdc++.h>
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i <= n; i++)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define V vector<int>
#define VP vector<pair<int, int> >
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
#ifdef _WIN32
#include <windows.h>
#define print(x) PRINT(x, #x)
template<typename T> inline const void PRINT(T VARIABLE, string NAME)
{
#ifndef ONLINE_JUDGE /// ONLINE_JUDGE IS DEFINED ON CODEFORCES
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute(hConsole, 10);
    cerr << NAME << " = " << VARIABLE;
    SetConsoleTextAttribute(hConsole, 7);
    cerr << '\n';
#endif
}
#else
#define print(x) 0
#endif
typedef long long ll;
typedef unsigned long long ull;
const ll INFLL = 2 * (ll)1e18 + 100;
const int INFINT = 2 * (int)1e9 + 100;
const double PI = atan(1) * 4;
const double EPS = 1e-12;
const int seed = 1e3 + 7;

const int MOD = 1e9 + 7; /// careful here (7 or 9, 66.. etc)
const int NMAX = 5 * 1e5 + 5;

const int CHARMAX = (1 << 10);
class InParsare
{
private:
    FILE *fin;
    char *buffer;
    size_t index_of_buffer;

    char read_character()
    {
        index_of_buffer++;
        if(index_of_buffer == CHARMAX)
        {
            fread(buffer, 1, CHARMAX, fin);
            index_of_buffer = 0;
        }
        return buffer[index_of_buffer];
    }

public:
    InParsare(const char *name)
    {
        fin = fopen(name, "r");
        buffer = new char[CHARMAX]();
        index_of_buffer = CHARMAX - 1;
    }

    template<class T>
    InParsare &operator >> (T &n)
    {
        char c;
        while(!isdigit(c = read_character()) && c != '-');

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

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

        return *this;
    }
};

class OutParsare
{
private:
    FILE *fout;
    char *buffer;
    size_t index_of_buffer;

    void write_character(char character)
    {
        if(index_of_buffer == CHARMAX)
        {
            fwrite(buffer, 1, CHARMAX, fout);
            index_of_buffer = 0;
            buffer[index_of_buffer++] = character;
        }
        else buffer[index_of_buffer++] = character;
    }

public:

    OutParsare(const char *name)
    {
        fout = fopen(name, "w");
        buffer = new char[CHARMAX]();
        index_of_buffer = 0;
    }

    ~OutParsare()
    {
        fwrite(buffer, 1, index_of_buffer, fout);
        fclose(fout);
    }
    template<class T>
    OutParsare &operator << (T n)
    {
        if(typeid(T).name() == typeid(char).name())
        {
            write_character(n);
            return *this;
        }

        if(n <= 9)
            write_character(n + '0');
        else
        {
            (*this) << (n / 10);
            write_character(n % 10 + '0');
        }

        return *this;
    }

};

InParsare fin("secventa.in");
OutParsare fout("secventa.out");
#define cin fin
#define cout fout

int n, k;
deque<pair<short, int> > d;


int main()
{
    FASTIO;
    cin >> n >> k;
    short a, sol = -30001;
    int l = k;
    cin >> a;
    if(n == 1) return cout << a, 0;
    d.pb(mp(a, 1));
    for(int i = 2; i <= n; i++)
    {
        cin >> a;
        if(i <= k)
        {
            if(a <= d[0].first)
                d.push_front(mp(a, i));
            else
            {
                while(!d.empty() && d.back().first >= a) d.pop_back();
                d.pb(mp(a, i));
            }
        }
        else
        {
            if(sol == -INFINT)
            {
                sol = d[0].first;
                l = k;
            }

            while(!d.empty() && d[0].second <= i - k) d.pop_front();

            if(d.empty() || a <= d[0].first)
                d.push_front(mp(a, i));
            else
            {
                while(!d.empty() && d.back().first >= a) d.pop_back();
                d.pb(mp(a, i));
            }

            if(sol < d[0].first)
            {
                sol = d[0].first;
                l = i;
            }
        }
    }


    cout << l - k + 1 << ' ' << l << ' ' << sol;
    return 0;
}