Cod sursa(job #2447193)

Utilizator ElizaTElla Rose ElizaT Data 12 august 2019 13:22:33
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;

deque<pair<int, int> > Q;
int n,x,k,inc,sf,k1,nr,semn,ans = -200000000;
int v[500010];
char c[2000009];

int main()
{
    ifstream fin("secventa.in");
    ofstream fout("secventa.out");
    fin >> n >> k1;
    fin.get();
	semn = 1;
	fin.getline (c,2000000);
	for(int i = 0;c[i] != 0;i++) {
		if(c[i] == '-') {
			semn = -1;
			continue;
		}
		if(c[i] == ' ') {
            v[++k] = nr * semn;
            semn = 1;
            nr = 0;
		}
		else
            nr = nr * 10 + (c[i] - '0');
	}
	v[++k] = nr;
	k = k1;
    inc = sf = 1;
    for(int i = 1;i <= n;i++)
    {
        while(Q.size() && Q.back().second > v[i])
            Q.pop_back();
        Q.push_back(make_pair(i, v[i]));
        if(Q.front().first == i - k)
              Q.pop_front();
        if(Q.front().second > ans && i >= k) {
            ans = Q.front().second;
            inc = i - k + 1;
            sf = i;
        }
    }
    fout << inc << ' ' << sf << ' ' << ans;
    return 0;
}