Cod sursa(job #2658759)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 14 octombrie 2020 22:28:02
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <deque>

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

struct yike{
	int v, p;
};

int n, k;
struct dequeseason2{
	yike yoke[500041];
	int lt=0, rt=0;
	bool empty(){return lt>=rt;}
	yike &front(){return yoke[lt];}
	yike &back(){return yoke[rt-1];}
	void pop_front(){lt++;}
	void pop_back(){rt--;}
	void push_back(yike yi){yoke[rt]=yi;rt++;}
};
dequeseason2 de;

struct wans{
	int lt, rt;
	int dio;
	bool valid = false;
};
wans ans;

int main(){
	ios_base::sync_with_stdio(false);
	fin >> n >> k;
	for(int i = 1; i <= n; ++i){
		int a;fin>>a;
		
		if(!de.empty() && i-de.front().p >= k)de.pop_front();
		while(!de.empty() && a<=de.back().v)de.pop_back();
		de.push_back({a,i});
		
		yike &y = de.front();
		if(i >= k && (!ans.valid || y.v > ans.dio)){
			ans.dio = y.v;
			ans.lt = i-k+1;
			ans.rt = i;
			ans.valid = true;
		}
	}
	fout << ans.lt << " " << ans.rt << " " << ans.dio;
	return 0;
}