Pagini recente » Cod sursa (job #1941114) | Cod sursa (job #1244527) | Cod sursa (job #607731) | Cod sursa (job #1903624) | Cod sursa (job #703375)
Cod sursa(job #703375)
#include <stdio.h>
#include <vector>
using namespace std;
#define MAXN 500005
#define MAXDIFNR 600020
#define MAXNR 30000
vector<int> poz[MAXDIFNR];
int n, k, nrInterv = 1, indice;
pair<int, int> intervale[MAXN];
vector<int> subinterv[MAXN];
pair<int, int> interv;
bool intervBun;
void dfs(int nod)
{
if(subinterv[nod].empty())
{
interv.first = intervale[nod].first + 1;
interv.second = intervale[nod].second - 1;
intervBun = true;
nrInterv++;
subinterv[nod].push_back(nrInterv);
intervale[nrInterv] = pair<int, int> (interv.first - 1, indice);
nrInterv++;
subinterv[nod].push_back(nrInterv);
intervale[nrInterv] = pair<int, int> (indice, interv.second + 1);
return;
}
vector<int>::iterator it;
for(it = subinterv[nod].begin(); it != subinterv[nod].end(); it++)
{
if(intervale[*it].second > indice)
{
if(intervale[*it].second - intervale[*it].first > k)
dfs(*it);
else
return;
}
}
}
int nr[MAXN];
int main()
{
FILE *in = fopen("secventa.in", "r");
FILE *out = fopen("secventa.out", "w");
fscanf(in, "%i %i", &n, &k);
intervale[1] = pair<int, int>(0, n + 1);
int i, aux, j, maxim = -30001;
pair<int, int> maxinterv;
for(i = 1 ;i <= n; i++)
{
fscanf(in, "%i", &nr[i]);
}
for(i = 1; i <= n; i++)
{
if(nr[i] > maxim)
{
for(j = i - 1; j > 0; j--)
if(nr[j] < nr[i])
break;
interv.first = j + 1;
for(j = i + 1; j <= n; j++)
if(nr[j] < nr[i])
break;
interv.second = j - 1;
if(interv.second - interv.first >= k - 1)
{
maxinterv.first = interv.first;
maxinterv.second = interv.first + k - 1;
maxim = nr[i];
}
}
}
fprintf(out, "%i %i %i\n", maxinterv.first, maxinterv.second, maxim);
/*for(i = 1; i <= n; i++)
{
fscanf(in, "%i", &aux);
poz[aux + MAXNR].push_back(i);
}
vector<int>::iterator it;
pair<int, int> intervMax;
bool gasit;
int maxim;
for(i = 0; i < MAXDIFNR; i++)
{
if(!poz[i].empty())
{
gasit = false;
for(it = poz[i].begin(); it != poz[i].end(); it++)
{
intervBun = false;
indice = *it;
dfs(1);
if(intervBun == true && gasit == false)
{
gasit = true;
intervMax.first = interv.first;
intervMax.second = interv.second;
maxim = i;
}
}
}
}
fprintf(out, "%i %i %i\n", intervMax.first + 1, intervMax.first + k, maxim - MAXNR);*/
}