Pagini recente » Cod sursa (job #2604126) | Cod sursa (job #727686) | Cod sursa (job #63254) | Cod sursa (job #2778599) | Cod sursa (job #1456282)
#include <fstream>
#include <deque>
using namespace std;
deque <pair <int, int> > d;
void insertInDeque(int value, int position)
{
if(d.empty())
{
d.push_back(make_pair(value, position));
return;
}
int left = -1;
int right = d.size();
int mid;
while(left + 1 < right)
{
mid = (left + right) / 2;
if(value < d[mid].first)
right = mid;
else
left = mid;
}
d.insert(d.begin() + left + 1, make_pair(value, position));
d.erase(d.begin() + left + 2, d.end());
}
/*void insertInDeque(int value, int position)
{
if(d.empty())
{
d.push_back(make_pair(value, position));
return;
}
int left = 0;
int right = d.size() - 1;
int mid;
while(left + 1 < right)
{
mid = (left + right) / 2;
if(value <= d[mid].first)
right = mid;
else
left = mid + 1;
}
d.insert(d.begin() + right, make_pair(value, position));
d.erase(d.begin() + right + 1, d.end());
}*/
int getFromDeque(int left)
{
deque <pair <int, int> > :: iterator it;
for(it = d.begin(); it != d.end(); it++)
if(it->second >= left)
break;
d.erase(d.begin(), it);
return it->first;
}
int main()
{
int n, k;
int left, right;
int bestL, bestR, bestB;
int value;
ifstream f("secventa.in");
f >> n >> k;
for(right = 1; right <= k; right++)
{
f >> value;
insertInDeque(value, right);
}
bestL = 1; bestR = k; bestB = getFromDeque(1);
for(left = 2; right <= n; left++, right++)
{
f >> value;
insertInDeque(value, right);
value = getFromDeque(left);
if(value > bestB)
{
bestB = value;
bestL = left;
bestR = right;
}
}
ofstream g("secventa.out");
g << bestL << " " << bestR << " " << bestB << "\n";
g.close();
return 0;
}