Cod sursa(job #2594392)

Utilizator Horia14Horia Banciu Horia14 Data 5 aprilie 2020 21:09:32
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<cstdio>
#include<cctype>
#include<deque>
#include<vector>
#define MAX_N 500000
#define BUF_SIZE 1 << 18

char buf[BUF_SIZE];
int pos = BUF_SIZE;
std::vector<int> v;
std::deque<int> dq;

inline char getChar(FILE* fin) {
    if(pos == BUF_SIZE) {
        fread(buf, 1, BUF_SIZE, fin);
        pos = 0;
    }
    return buf[pos++];
}

inline int read(FILE* fin) {
    int res, s;
    char ch;
    res = 0;
    s = 1;
    do {
        ch = getChar(fin);
        if(ch == '-')
            s = -s;
    }while(!isdigit(ch));
    do {
        res = 10*res + ch - '0';
        ch = getChar(fin);
    }while(isdigit(ch));
    return res * s;
}

int main() {
    int n, k, x, maxim, b, e;
    FILE* fin, *fout;
    fin = fopen("secventa.in", "r");
    fout = fopen("secventa.out", "w");
    n = read(fin);
    k = read(fin);
    maxim = -30001;
    b = e = -1;
    for(int i = 0; i < n; ++i) {
        x = read(fin);
        v.push_back(x);
        if(!dq.empty() && i - dq.front() >= k)
            dq.pop_front();

        while(!dq.empty() && v[i] <= v[dq.back()])
            dq.pop_back();
        dq.push_back(i);
        if(i >= k - 1) {
            if(maxim < v[dq.front()]) {
                maxim = v[dq.front()];
                e = i;
                b = i - k + 1;
            }
        }
    }
    fprintf(fout,"%d %d %d\n", b + 1, e + 1, maxim);
    fclose(fin);
    fclose(fout);
    return 0;
}