Cod sursa(job #2546891)

Utilizator marius004scarlat marius marius004 Data 14 februarie 2020 18:19:30
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#include <deque>
 
std::ifstream f("secventa.in");
std::ofstream g("secventa.out");
 
const int NMAX = 500005;
int n,k,v[NMAX],sol,I,J,maxx,maxxIndex;
std::deque<int>d;

int getDistance(int x,int y){
	return y - x + 1;
} 
 
int main(){
 
    f >> n >> k;
 
    // din fiecare secventa de lungime k iau minimul si il compar cu maximul curent
    //numarul obtinut este valoarea maxima a bazei.mai trebuie sa iau indexul minim
    for(int i = 1;i <= n;++i){
 
        f >> v[i];
 
        while(!d.empty() && v[i] <= v[d.back()])
            d.pop_back();
 
        d.push_back(i);
 
        if(i - d.front() + 1 > k)
            d.pop_front();
 
        if(i >= k && v[d.front()] > maxx){
            maxx = v[d.front()];
            maxxIndex = d.front();
        }
    }
 
    int I = maxxIndex;
    int J = maxxIndex;
 
    while(I - 1 >= 1 && v[I - 1] >= maxx)
        I--;
    
    if(J - I + 1 >= k)
    	g << I << " " << " " << J << " " << maxx; 
	else{
		
		while(J + 1 <= n && getDistance(I,J) < k && v[J + 1] >= maxx)
			J++;
		
		g << I << " " << J << " " << maxx; 
	}
 
    return 0;
}