Submission #1251017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251017		ogkostya	Triple Peaks (IOI25_triples)	C++20	60.25 / 100	2110 ms	560176 KiB

triples

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

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));
    }
  }

  std::vector<std::vector<int>> p(4 * 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)
        s[i].insert(std::pair<int, int>(j, k));
    }
    p[3 * n + i - H[i]].push_back(i);
  }
  std::vector<std::vector<int>> p2(2 * n, std::vector<int>());
  for (int j = n - 1; j > 0; j--)
  {
    p[3 * n + j - H[j]].pop_back();

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

    p2[j + H[j]].push_back(j);
  }

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

  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)
{
  std::vector<int> ans(M, 1);
  for (int i = 0; i < M; i++)
  {
    ans[i] = array[i % 14];
  }
  return ans;
}

• 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: 0 / 19
• Subtask 7: 5 / 5
• Subtask 8: 2.3075 / 5
• Subtask 9: 0.9278 / 5
• Subtask 10: 0.3979 / 5
• Subtask 11: 0.4643 / 5
• Subtask 12: 0.1548 / 5