Pagini recente » Istoria paginii runda/simulare_oji_2023_clasa_9_16_martie | Cod sursa (job #1371794) | Cod sursa (job #3140540) | Cod sursa (job #2308539) | Cod sursa (job #2191648)
#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, AN, vf;
char WT[10000001];
int main()
{
fin >> N >> K;
fin.get();
fin.getline(WT, 10000001);
signstring = 1;
vf = 1;
for (i = 0; i <= strlen(WT+1); i++) {
if(WT[i]==' '){
NR[vf++] = (AN*signstring);
AN = 0;
signstring = 1;
}
else if(WT[i]=='-') signstring = -1;
else AN = AN * 10 + (WT[i] - '0');
}
NR[N] = AN * 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;
}