Pagini recente » Cod sursa (job #525442) | Cod sursa (job #2625687) | Cod sursa (job #2350311) | Cod sursa (job #550280) | Cod sursa (job #741827)
Cod sursa(job #741827)
#include <iostream>
#include <fstream>
#include <deque>
#include <string.h>
using namespace std;
const char infile[] = "secventa.in";
const char outfile[] = "secventa.out";
#define NMAX 500001
struct NumberInfo
{
int value;
int position;
NumberInfo()
{
}
NumberInfo(int value, int position)
{
this->value = value;
this->position = position;
}
};
int readNextInt(char* sir)
{
char* p = sir;
int result = 0;
bool isNegative = false;
if(*p == '-')
{
p++;
isNegative = true;
}
while(*p)
{
result *= 10;
result += *p - '0';
p++;
}
if(isNegative == true)
result = -result;
return result;
}
char sir [NMAX * 8];
void solve( istream &cin, ostream &cout )
{
deque<NumberInfo> deq;
int sequenceLength;
int numbersCount;
cin >> numbersCount
>> sequenceLength;
cin.getline(sir, 1);
cin.getline(sir, NMAX * 8);
int currentNumber;
int sequenceStart;
int sequenceBase;
char *p;
p = strtok(sir, " ");
currentNumber = readNextInt(p);
deq.push_back(NumberInfo(currentNumber, 0));
for(int i = 1; i < numbersCount; i++)
{
p = strtok(NULL, " ");
currentNumber = readNextInt(p);
if(deq.empty() == false && deq.front().position <= i - sequenceLength)
{
deq.pop_front();
}
while(deq.empty() == false && deq.back().value > currentNumber)
{
deq.pop_back();
}
deq.push_back(NumberInfo(currentNumber, i));
if(i >= sequenceLength)
{
if(deq.front().value > sequenceBase)
{
sequenceBase = deq.front().value;
sequenceStart = i - sequenceLength + 1;
}
}
else if(i == sequenceLength - 1)
{
sequenceStart = 0;
sequenceBase = deq.front().value;
}
}
sequenceStart += 1;
cout << sequenceStart << " "
<< sequenceStart + sequenceLength - 1 << " "
<< sequenceBase << "\n";
}
int main(int argc, char* argv[])
{
fstream fin(infile, ios::in);
fstream fout(outfile, ios::out);
solve(fin, fout);
fin.close();
fout.close();
}