Pagini recente » Cod sursa (job #2109937) | Cod sursa (job #883507) | Cod sursa (job #972678) | Cod sursa (job #2760956) | Cod sursa (job #2191643)
#include <fstream>
#include <cstring>
#include <deque>
#define NMax 500002
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
deque <int> MinS, MinP;
int N, i, K, drmin, minx, NR[NMax], signstring, actualnumberwearegonnause, vf;
char whyteachusaboutbasicreadingifthisismoreefficient[10000001];
int main()
{
fin >> N >> K;
fin.get();
fin.getline(whyteachusaboutbasicreadingifthisismoreefficient, 10000001);
signstring = 1;
vf = 1;
for (i = 0; i <= strlen(whyteachusaboutbasicreadingifthisismoreefficient+1); i++) {
if(whyteachusaboutbasicreadingifthisismoreefficient[i]==' '){
NR[vf++] = (actualnumberwearegonnause*signstring);
actualnumberwearegonnause = 0;
signstring = 1;
}
else if(whyteachusaboutbasicreadingifthisismoreefficient[i]=='-') signstring = -1;
else actualnumberwearegonnause = actualnumberwearegonnause * 10 + (whyteachusaboutbasicreadingifthisismoreefficient[i] - '0');
}
NR[N] = actualnumberwearegonnause * signstring;
for (i = 1; i <= K; i++) {
while (!MinS.empty() && NR[i] < MinS.back()) {
MinS.pop_back();
MinP.pop_back();
}
MinS.push_back(NR[i]);
MinP.push_back(i + 1);
}
minx = MinS.front();
drmin = K;
for(i=K+1; i<=N; i++){
if ((i - MinP.front()) >= K) {
MinS.pop_front();
MinP.pop_front();
}
while (!MinS.empty() && (NR[i] < MinS.back())) {
MinS.pop_back();
MinP.pop_back();
}
MinS.push_back(NR[i]);
MinP.push_back(i);
if (MinS.front() > minx) {
drmin = i;
minx = MinS.front();
}
}
fout << drmin - K + 1 << " " << drmin << " " << minx;
return 0;
}