Pagini recente » Cod sursa (job #1261081) | Utilizatori inregistrati la Infoarena Monthly 2012 - Runda 10 | Cod sursa (job #1407994) | Cod sursa (job #875870) | Cod sursa (job #2312384)
#include <iostream>
#include <fstream>
using namespace std;
int n, k;
int binsearch(int* vec, int start, int end, int value)
{
int medp;
if(start > end) { medp = ((start+end+k)/2)%k; }
else medp = (start+end)/2;
if(value == vec[medp]) return medp;
if(end-start < 2)
{
if(value < vec[medp]) return medp;
else return medp+1;
}
if(value < vec[medp]) return binsearch(vec, start, medp, value);
else return binsearch(vec, medp, end, value);
}
int main()
{
ifstream fin("secventa.in");
int qpos = 0;
fin>>n>>k;
int* datavec = new int[n];
int* queue = new int[k];
int* bpos = new int[k];
int ringstart = 0;
queue[qpos] = 50000;
int maxbasis = -50000;
int maxbasispost = -1;
fin>>datavec[0];
queue[qpos] = datavec[0];
bpos[qpos] = 0;
qpos++;
for(int i=1;i<k;i++)
{
fin>>datavec[i];
int pos;
if(datavec[i]<queue[qpos])
pos = binsearch(queue, 0, qpos, datavec[i]);
else pos = qpos;
qpos = pos;
queue[qpos] = datavec[i];
bpos[qpos] = i;
qpos++;
}
for(int i=k;i<n;i++)
{
fin>>datavec[i];
int pos;
if(datavec[i]<queue[qpos-1])
pos = binsearch(queue, ringstart%k, qpos, datavec[i]);
else pos = qpos;
qpos = pos;
queue[qpos] = datavec[i];
bpos[qpos] = i;
qpos++;
if(i-bpos[ringstart] >= k) { ringstart++; }
if(queue[ringstart] > maxbasis) { maxbasis = queue[ringstart]; maxbasispost = bpos[ringstart]; }
}
int lowpoint;
for(lowpoint=maxbasispost;lowpoint>=0;lowpoint--)
if(datavec[lowpoint] < maxbasis) break;
lowpoint++;
int endpoint = lowpoint+k;
ofstream fout("secventa.out");
fout<<lowpoint+1<<" "<<endpoint<<" "<<maxbasis;
return 0;
}