Pagini recente » Cod sursa (job #2437291) | Cod sursa (job #2542237) | Cod sursa (job #405996) | Cod sursa (job #1420360) | Cod sursa (job #741821)
Cod sursa(job #741821)
#include <iostream>
#include <fstream>
#include <deque>
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 A[NMAX];
NumberInfo elements[NMAX];
class Deque
{
public:
Deque(int maxSize)
{
this->_start = -1;
this->_end = -1;
this->_elements = (NumberInfo *) &elements;
}
~Deque()
{
}
NumberInfo front()
{
return this->_elements[_start];
}
NumberInfo back()
{
return this->_elements[_end];
}
bool empty()
{
if(_end < _start || this->_start == -1)
return true;
return false;
}
void pop_back()
{
this->_end --;
}
void push_back(NumberInfo element)
{
if(this->empty() == true)
{
this->_start = 0;
this->_end = -1;
}
this->_end++;
this->_elements[_end] = element;
}
void pop_front()
{
this->_start++;
}
protected:
private:
int _start;
int _end;
NumberInfo *_elements;
};
void readInput(int &numbersCount, int& sequenceLength, int * numbers, istream &cin)
{
cin >> numbersCount
>> sequenceLength;
for(int i = 0 ; i < numbersCount; i++)
{
cin >> numbers[i];
}
}
void solve(int &numbersCount, int& sequenceLength, int * numbers, ostream &cout)
{
//deque<NumberInfo> deq;
Deque deq(numbersCount);
int sequenceStart;
int sequenceBase;
deq.push_back(NumberInfo(numbers[0], 0));
for(int i = 1; i < sequenceLength; i++)
{
while(deq.empty() == false && deq.back().value > numbers[i])
{
deq.pop_back();
}
deq.push_back(NumberInfo(numbers[i], i));
}
sequenceStart = 0;
sequenceBase = deq.front().value;
for(int i = sequenceLength; i < numbersCount; i++)
{
if(deq.front().position <= i - sequenceLength)
{
deq.pop_front();
}
while(deq.empty() == false && deq.back().value > numbers[i])
{
deq.pop_back();
}
deq.push_back(NumberInfo(numbers[i], i));
if(deq.front().value > sequenceBase)
{
sequenceBase = deq.front().value;
sequenceStart = i - sequenceLength + 1;
}
}
sequenceStart += 1;
cout << sequenceStart << " "
<< sequenceStart + sequenceLength - 1 << " "
<< sequenceBase << "\n";
}
int main(int argc, char* argv[])
{
int numbersCount;
int sequenceLength;
int *numbers = (int*)&A;
fstream fin(infile, ios::in);
readInput(numbersCount, sequenceLength, numbers, fin);
fin.close();
fstream fout(outfile, ios::out);
solve(numbersCount, sequenceLength, numbers, fout);
fout.close();
}