Pagini recente » Cod sursa (job #300277) | Cod sursa (job #300292) | Cod sursa (job #272702) | Cod sursa (job #2195458) | Cod sursa (job #1456290)
#include <fstream>
#include <deque>
using namespace std;
deque <pair <int, int> > d;
char seq[3500001];
char * start;
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 readV()
{
int sgn = 1;
int value = 0;
while(*start == ' ')
start++;
if(*start == '-')
{
sgn = -1;
start++;
}
while(*start != '\0' && *start >= '0' && *start <= '9')
{
value = value * 10 + *start - '0';
start++;
}
return value * sgn;
}
int main()
{
int n, k;
int left, right;
int bestL, bestR, bestB;
int value;
ifstream f("secventa.in");
f >> n >> k;
f.getline(seq, 3500000);
f.getline(seq, 3500000);
start = seq;
f.close();
for(right = 1; right <= k; right++)
{
value = readV();
insertInDeque(value, right);
}
bestL = 1; bestR = k; bestB = getFromDeque(1);
for(left = 2; right <= n; left++, right++)
{
value = readV();
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;
}