Cod sursa(job #2579875)

Utilizator Dragos1226Dragos Chileban Dragos1226 Data 12 martie 2020 22:54:37
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<fstream>
#include<queue>
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");
const int NMax = 500000;
deque <int> Q;
pair <int, int> Sol;
int N, K, A[NMax+5];
char s[2000005];
bool sign;
void Init() {
    in.get();
    in.getline(s, sizeof(s));
    N = 0;
    for (int i=0; s[i]; i++) {
        int Nr;
        if (s[i] >= '0' && s[i] <= '9') {
            if (s[i-1] == '-')
                sign = true;
            else
                sign = false;

            Nr = 0;
            while (s[i] >= '0' && s[i] <= '9') {
                Nr = Nr * 10 + s[i] - '0';
                i++;
            }
            i--;
            if (sign)
            Nr = -Nr;
            N++, A[N] = Nr;
          }
       }
}

void Solve() {
    Sol.first = -1e9;
    for (int i = 1; i <= N; i++) {
        while (!Q.empty() && A[i] < A[Q.back()])
            Q.pop_back();
        Q.push_back(i);
        if (!Q.empty() && Q.front() <= i-K)
            Q.pop_front();
        if (!Q.empty() && i >= K)
            if (A[Q.front()] > Sol.first)
                Sol.first = A[Q.front()], Sol.second = i;

    }
    out << Sol.second-K+1 << " " << Sol.second << " " << Sol.first << '\n';
}

int main() {
    in >> N >> K;
    Init();
    Solve();
}