Submission #1275203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275203		strange420	3개의 봉우리 (IOI25_triples)	C++20	79.24 / 100	209 ms	32980 KiB

triples

#include "triples.h"

long long count_triples(std::vector<int> H) {
  std::vector<std::vector<int>> asd (H.size());
  for (int i=0; i<H.size(); i++)
    asd[H[i]].push_back(i);

  std::vector<std::vector<int>> cache(H.size());
  for (int i=0; i<H.size(); i++)
    if (i-H[i] >= 0)
      cache[i-H[i]].push_back(i);

  long long ans = 0;
  for (int i=0;i<H.size(); i++) {
    if (i + H[i] >= H.size()) continue;
    int sub_peak_index = H[i] + i;

    // One case - special case
    for (int x: cache[i+H[i]]) { // cba
      if (H[x] + i >= H.size()) continue;
      int sub_peak = H[x] + i;
      if (H[sub_peak] == H[i] + H[x])
        ans++;
    }

    if (i + H[sub_peak_index] < H.size()) { // abc
      int last = i + H[sub_peak_index];
      if (H[i] + H[last] == H[sub_peak_index] && H[i] != H[last])
        ans++;
    }

    if (i + H[sub_peak_index] < H.size()) { // cab
      int last = i + H[sub_peak_index];
      if (H[i] == H[sub_peak_index] + H[last])
        ans++;
    }

    if (sub_peak_index - H[sub_peak_index] >= 0) { // bac
      int last = H[i] + i - H[sub_peak_index];
      if (H[last] + H[sub_peak_index] == H[i] && H[last] != H[sub_peak_index])
        ans ++;
    }

    for (int sub_peak_index: cache[i]) { // bca
      if (sub_peak_index - H[i] < 0) continue;
      int last = sub_peak_index - H[i];
      if (H[last] + H[i] == H[sub_peak_index])
        ans++;
    }

    if (sub_peak_index + H[sub_peak_index] <= H.size()) { // acb
      int last = sub_peak_index + H[sub_peak_index];
      if (H[last] == H[i] + H[sub_peak_index] && H[i] != H[sub_peak_index])
        ans ++;
    }
  }

  return ans;
}

std::vector<int> construct_range(int M, int K) {
  std::vector<int> ans, base  = {1, 2, 1, 4, 3, 2, 7, 6, 5, 6, 3, 4, 5, 1};
  for (int i=0; i<M; i++)
    ans.push_back(base[i%base.size()]);
  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: 19 / 19
• Subtask 7: 5 / 5
• Subtask 8: 2.3 / 5
• Subtask 9: 0.9279 / 5
• Subtask 10: 0.3979 / 5
• Subtask 11: 0.4643 / 5
• Subtask 12: 0.1548 / 5