Pagini recente » Cod sursa (job #311196) | Cod sursa (job #1212512) | Cod sursa (job #2839686) | Cod sursa (job #1997252) | Cod sursa (job #2573941)
/*#include <iostream>
#include <fstream>
#include <queue>
#define INF 999999
#define MINF -999999
using namespace std;
typedef struct sequence
{
int n = 0;
deque < int > numbers;
int base = INF;
}seq;
typedef struct result
{
int start = 0;
int finish = 0;
int base = MINF;
}res;
ifstream fin;
ofstream fout;
int n, k;
seq readFirstSequence()
{
seq sequence;
sequence.n = k;
for (int i = 1; i <= k; i++)
{
int nr;
fin >> nr;
sequence.numbers.push_back(nr);
if (nr < sequence.base)
sequence.base = nr;
}
return sequence;
}
void insertNrInSeq(int number, seq &seq)
{
seq.numbers.push_back(number);
if (number < seq.base)
seq.base = number;
}
void writeSeq(seq seq)
{
while(seq.n > 0)
{
seq.n--;
cout << seq.numbers.front() << " ";
seq.numbers.pop_front();
}
cout << '\n';
}
int findBase(seq seq)
{
int base = INF;
while(seq.n > 0)
{
seq.n--;
if (seq.numbers.front() < base)
base = seq.numbers.front();
seq.numbers.pop_front();
}
return base;
}
void updateResult(res &res, seq seq, int start, int finish)
{
if (seq.base > res.base)
{
res.base = seq.base;
res.start = start;
res.finish = finish;
}
}
int main() {
fin.open("secventa.in");
fout.open("secventa.out");
fin >> n >> k;
seq seq = readFirstSequence();
res res;
//writeSeq(seq);
for (int i = k+1; i <= n; i++)
{
int number;
fin >> number;
seq.numbers.push_back(number);
if (number <= seq.base) {
seq.base = number;
seq.numbers.pop_front();
} else {
if (seq.base == seq.numbers.front()) {
seq.numbers.pop_front();
seq.base = findBase(seq);
} else
seq.numbers.pop_front();
}
//writeSeq(seq);
updateResult(res, seq, i-k+1, i);
//cout << seq.base << '\n';
}
fout << res.start << " " << res.finish << " " << res.base;
fin.close();
fout.close();
return 0;
}*/
#include <fstream>
#include <deque>
#include <string>
#define NMAX 500001
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
deque < int > dq;
int n, k;
int v[NMAX];
string s;
int toNumber(int &index)
{
while (s[index] == ' ')
++index;
char sign = '+';
if (s[index] == '-') {
sign = '-';
++index;
}
int nr = 0;
while (s[index] >= '0' && s[index] <= '9') {
nr = nr*10 + (s[index] -'0');
++index;
}
if (sign == '+')
return nr;
return -nr;
}
int main()
{
fin >> n >> k;
fin.get();
getline(fin, s);
int index = 0;
int maximum = -30005, left, right;
for (int i = 1; i <= n; i++)
{
v[i] = toNumber(index);
while (!dq.empty() && v[i] <= v[dq.back()])
dq.pop_back();
dq.push_back(i);
if (i - dq.front() + 1 > k)
dq.pop_front();
if (maximum < v[dq.front()] && i >= k)
{
maximum = v[dq.front()];
right = i;
left = i - k + 1;
}
}
fout << left << ' ' << right << ' ' << maximum;
}