Pagini recente » Cod sursa (job #854688) | Cod sursa (job #2969191) | Cod sursa (job #2563117) | Cod sursa (job #848091) | Cod sursa (job #2447145)
#include <iostream>
#include <cstdio>
#include <vector>
#define OFFSET 30000
#define MAXINT 30000
#define NMAX 500010
#define MININT -30010
using namespace std;
vector<int> pos[60002];
int n, k;
int x;
int repr[NMAX];
int len[NMAX];
int chainJoin(int i)
{
if (repr[i] == i)
return i;
repr[i] = chainJoin(repr[i]);
return repr[i];
}
int merge(int i)
{
if (repr[i - 1])
{
repr[i] = chainJoin(i - 1);
len[repr[i]] += 1;
}
else
{
repr[i] = i;
len[i] = 1;
}
if (repr[i + 1])
{
repr[i + 1] = repr[i];
len[repr[i]] += len[i + 1];
}
return (len[repr[i]] >= k);
}
int main()
{
freopen("secventa.in", "r", stdin);
freopen("secventa.out", "w", stdout);
scanf("%d", &n);
scanf("%d", &k);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &x);
pos[x + OFFSET].push_back(i);
}
for (int maxSupport = MAXINT + OFFSET; maxSupport >= 0; --maxSupport)
{
for (int i = 0; i < pos[maxSupport].size(); ++i)
{
int currentPos = pos[maxSupport][i];
if (merge(currentPos))
{
printf("%d %d %d", repr[currentPos], repr[currentPos] + k - 1, maxSupport - OFFSET);
return 0;
}
}
}
return 0;
}