Submission #1253229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253229		ogkostya	Triple Peaks (IOI25_triples)	C++20	100 / 100	1403 ms	37056 KiB

triples

#include "triples.h"
#include <set>
#include <cstdio>

long long count_triples(std::vector<int> H)
{

  int n = H.size();
  // if (n < 1000000)
  //   return 0;
  std::vector<std::set<std::pair<int, int>>> s(n, std::set<std::pair<int, int>>());

  for (int j = 1; j < n - 1; j++)
  {
    int i, k;
    i = j - H[j];
    if (i >= 0)
    {
      k = j + H[i];
      if (k < n && k - i == H[k])
        s[i].insert(std::pair<int, int>(j, k));

      k = i + H[i];
      if (k < n && k > j && H[k] == k - j)
        s[i].insert(std::pair<int, int>(j, k));
    }

    k = j + H[j];
    if (k < n)
    {
      i = j - H[k];
      if (i >= 0 && k - i == H[i])
        s[i].insert(std::pair<int, int>(j, k));
      i = k - H[k];
      if (i >= 0 && i < j && j - i == H[i])
        s[i].insert(std::pair<int, int>(j, k));
    }
  }

  long long ans = 0;
  for (int i = 0; i < s.size(); i++)
  {
    ans += s[i].size();
  }

  std::vector<std::vector<int>> l(n, std::vector<int>());
  std::vector<std::vector<int>> r(n, std::vector<int>());
  for (int i = 0; i < n; i++)
  {
    int j = i + H[i];
    if (j < n)
    {
      int k = i + H[j];
      if (k < n && k > j && k - H[k] == j)
        ans++;

      l[j].push_back(i);
    }
    {
      int k = i - H[i];
      if (k >= 0)
        r[k].push_back(i);
    }
  }

  for (int jj = 0; jj < n; jj++)
  {
    if (l[jj].size() == 0 || r[jj].size() == 0)
      continue;
    if (1LL * l[jj].size() * r[jj].size() <= n)
    {
      for (const int &i : l[jj])
      {
        for (const int &k : r[jj])
        {
          if (H[i] == H[k])
            continue;
          int j = i + H[k];
          if (H[j] == k - i)
          {
            ans++;
            // printf("%d %d\n", j, i + H[i]);
          }
        }
      }
    }
    else
    {
      for (int j = jj - 1; j >= 0; j--)
      {
        int d = jj - j;
        if (d < H[j])
          continue;
        d += H[j];
        if ((d & 1) == 1)
          continue;
        d >>= 1;
        int x = H[j] - d;
        if (x == d)
          continue;
        int i = jj - d;
        int k = jj + x;
        if (k - H[k] == jj && i + H[i] == jj)
        {
          ans++;
          // printf("%d %d\n", j, i + H[i]);
        }
      }

      for (int j = jj + 1; j < n; j++)
      {
        int d = j - jj;
        if (d < H[j])
          continue;
        d += H[j];
        if ((d & 1) == 1)
          continue;
        d >>= 1;
        int x = H[j] - d;
        if (x == d)
          continue;
        int i = jj - x;
        int k = jj + d;
        if (k - H[k] == jj && i + H[i] == jj)
        {
          ans++;
          // printf("%d %d\n", j, i + H[i]);
        }
      }
    }
  }

  return ans;
}

int array[] = {3, 1, 2, 1, 4, 3, 2, 7, 6, 5, 6, 3, 4, 5};

std::vector<int> construct_range(int M, int K)
{
  if (M < 30)
  {
    std::vector<int> ans(M, 1);
    for (int i = 0; i < M; i++)
    {
      ans[i] = array[i % 14];
    }
    return ans;
  }
  else
  {
    std::vector<int> ans(M, 0);
    std::vector<int> s(2 * M, 1);
    std::vector<int> z(0);
    std::vector<bool> f(2 * M, false);
    f[0] = true;
    s[1] = -1000000;
    z.push_back(-1);
    z.push_back(1);
    ans[0] = 1;

    int count = 1;
    while (count < M)
    {
      int y = 1;
      for (int i = 3; i < s.size(); i += 2)
      {
        if (s[y] < s[i])
          y = i;
      }

      for (int &x : z)
      {
        if (y + x < 2 * M && !f[y + x])
        {
          ans[(y + x) / 2] = std::abs(y - x) / 2;
          count++;

          f[y + x] = true;

          for (int &q : z)
          {
            int w = y + x - q;
            if (w >= 0 && w < 2 * M)
            {
              s[w]--;
            }
          }
        }
      }
      z.push_back(y);
      for (int i = 3; i + y < 2 * M; i += 2)
        if (!f[i + y])
          s[i]++;
      s[y] = -1000000;

      // print(ans, s, 1);
    }
    //printf("%d\n", z.size());
    return ans;
  }
}

void print(std::vector<int> H, std::vector<int> s, int mod)
{
  int N = H.size();
  std::vector<int> X(N), Y(N);
  int maxx = 0, minx = N, maxy = 0, miny = N;
  printf("%d\n", N);
  for (int i = 0; i < N; i++)
  {
    X[i] = i - H[i];
    Y[i] = i + H[i];
    if (H[i] == 0)
    {
      Y[i] = 1;
      X[i] = -1;
    }

    maxx = std::max(maxx, X[i]);
    minx = std::min(minx, X[i]);

    maxy = std::max(maxy, Y[i]);
    miny = std::min(miny, Y[i]);
    printf("%d%c", H[i], " \n"[i + 1 == N]);
  }

  int sizex = maxx - minx + 1;
  int sizey = maxy - miny + 1;
  std::vector<std::vector<char>> map(sizey, std::vector<char>(sizex, ' '));
  std::vector<int> F(sizey);
  for (int i = 0; i < N; i++)
  {
    F[maxy - Y[i]] = Y[i];

    map[maxy - Y[i]][X[i] - minx] = '*';

    int x = X[i] - minx - 1;
    int y = maxy - Y[i] - 1;

    while (y >= 0 && x >= 0)
    {
      map[y][x] = '.';
      y--;
      x--;
    }
  }

  for (int i = 0; i < sizey; i++)
  {
    if (F[i] != 0)
    {
      printf("%4d", F[i]);
    }
    else
    {
      printf("    ");
    }
    for (int j = 0; j < sizex; j++)
    {
      printf("%c", map[i][j]);
    }
    int y = maxy - i;
    if (!s.empty() && y % 2 == mod)
    {
      printf("%d", s[y]);
    }
    printf("\n");
  }
  printf("%d\n", minx);
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 11 / 11
• Subtask 5: 16 / 16
• Subtask 6: 19 / 19
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5