Submission #1259706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259706		rxlfd314	Triple Peaks (IOI25_triples)	C++20	72.65 / 100	437 ms	31304 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

ll count_triples(vt<int> H) {
	const int N = size(H);
	ll ans = 0;
  set<ari3> s;
  const auto check = [&](const int i, const int j, const int k, bool bruh) {
    if (!(i < j && j < k && i >= 0 && k < N))
      return false;
    ari3 a = {j - i, k - i, k - j};
    ari3 b = {H[i], H[j], H[k]};
    sort(all(a));
    sort(all(b));
    if (a == b && bruh)
      s.insert({i, j, k});
    return a == b;
  };
  FOR(i, 1, N-2) {
    s.clear();
    if (i-H[i] >= 0) {
      check(i-H[i], i, i+H[i-H[i]], 1);
      check(i-H[i], i, i-H[i]+H[i-H[i]], 1);
    }
    if (i+H[i] < N) {
      check(i-H[i+H[i]], i, i+H[i], 1);
      check(i+H[i]-H[i+H[i]], i, i+H[i], 1);
    }
    ans += size(s);
  }
  FOR(i, 0, N-3) {
    const int j = i + H[i];
    if (j < N-1 && H[j] > H[i]) {
      const int k = i + H[j];
      ans += check(i, j, k, 0) && H[i] != H[k];
    }
  }
  // a < b < c
  // max(H[a], H[c]) < H[b]
  // b - a = H[c]
  // c - b = H[a]
  // c - a = H[b]
  // c - a = H[c] + H[a]
  // a + H[a] = c - H[c]
  // b - a + H[b] = H[c] + c - a
  // b + H[b] = c + H[c]
  // b - c - H[b] = -H[a] - c + a
  // b - H[b] = a - H[a]
  vt<vt<int>> d1(N<<1), d2(N<<1);
  FOR(i, 0, N-1) {
    d1[i-H[i]+N].push_back(i);
    d2[i+H[i]].push_back(i);
  }
  FOR(b, 1, N-2) {
    if (size(d1[b-H[b]+N]) < size(d2[b+H[b]]))
      for (const auto &a : d1[b-H[b]+N])
        ans += check(a, b, b + H[a], 0);
    else
      for (const auto &c : d2[b+H[b]])
        ans += check(b - H[c], b, c, 0);
  }
  return ans;
}

vt<int> construct_range(int M, int K) {
  vt<int> ret(M);
  FOR(i, 0, M-1)
    ret[i] = i % 2 + 1;
  return ret;
}

• 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: 1.5 / 5
• Subtask 8: 0.6225 / 5
• Subtask 9: 0.2499 / 5
• Subtask 10: 0.1071 / 5
• Subtask 11: 0.125 / 5
• Subtask 12: 0.0417 / 5