Cod sursa(job #2447140)

Utilizator claudiu.gatinaFMI Claudiu Gatina claudiu.gatina Data 12 august 2019 11:51:25
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#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];
}

bool 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("%hd", &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;
}