Pagini recente » Cod sursa (job #1029070) | Cod sursa (job #2191639)
#include <fstream>
#include <deque>
#include <cstring>
#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++) {
switch (whyteachusaboutbasicreadingifthisismoreefficient[i]) {
case ' ': {
NR[vf++] = (actualnumberwearegonnause*signstring);
actualnumberwearegonnause = 0;
signstring = 1;
break;
}
case '-': { signstring = -1; break;}
default: 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;
}