Cod sursa(job #1961013)
Utilizator | Oniga Mihai Mihai9 | Data | 10 aprilie 2017 20:41:00 |
---|---|---|---|
Problema | Secventa | Scor | 80 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.44 kb |
#include <fstream>
using namespace std;
int n,k,i,mini[500001],v[500001],maxi=-30001,p,u,st,dr;
ifstream f("secventa.in");
ofstream g("secventa.out");
int main(){
f>>n>>k;
for(i=1;i<=n;i++){f>>v[i];}
p=u=1;mini[p]=1;
for(i=2;i<=n;i++){
while(p<=u&&v[i]<=v[mini[u]]){u--;}
u++;mini[u]=i;
while(p<=u&&i-mini[p]>=k){p++;}
if(v[mini[p]]>maxi&&i>=k){maxi=v[mini[p]];dr=i;}
}
g<<dr-k+1<<" "<<dr<<" "<<maxi;
return 0;
}