Cod sursa(job #1765490)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 26 septembrie 2016 19:40:19
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <deque>
#define DIM 3000100
#define f first
#define s second
using namespace std;

char s[DIM];
deque<pair<int,int> > d;
int n,k,p;

void read(int &x) {
    x=0;
    bool sign=false;
    if(s[p]=='-')
        sign=true,p++;
    while(s[p]>='0'&&s[p]<='9')
        x=x*10+(s[p]-'0'),p++;
    p++;
    if(sign)
        x*=-1;
}

int main()
{
    ifstream fin("secventa.in");
    ofstream fout("secventa.out");
    fin.getline(s,DIM);
    read(n),read(k);
    fin.getline(s,DIM);
    p=0;
    int m,st,mx=-30000;
    for(int i=0;i<n;i++) {
        read(m);
        if(!d.empty()) {
            if(i>=k&&d.front().f>mx) {
                st=max(0,i-k);
                mx=d.front().f;
            }
            if(d.front().s<=i-k)
                d.pop_front();
        }
        while(!d.empty()&&d.back().f>m)
            d.pop_back();
        d.push_back({m,i});
    }
    if(d.front().f>mx) {
        st=n-k;
        mx=d.front().f;
    }
    fout<<st+1<<" "<<st+k<<" "<<mx;
    return 0;
}