D. Mysterious Crime

1700
  • Quiz
  • 補足
    • editorialがよくわからなかったので解説コードを紐解いてみた
    • 1人目の証言をrenumber（番号振り直し）する。permutationだからやってよい
    • あとは各iについて、i, i+1, i+2, ...がどこまで伸ばせるかを持つ(editorialでいうところのreach[i])
    • たとえばreach[3]=6なら、3,4,5,6が各証言に存在することを示している
    • これの長さは4
    • [3,4,5,6]には[3,4,5]や[4,5,6],[3],[4,5]なども含まれるので、combinationで一気に数える
    • [3]は範囲の値として[3,3]と選んだとして数えると、長さLの時は (L+1)*L/2 となる（下記画像参照）

f:id:peroon:20200901161831p:plain

test case (because sample is weak...)

4 3
1 2 3 4
2 3 1 4
4 1 2 3

// 2 3 is common
// ans = 5
5

something like editorial code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using VI = vector<ll>;
using VV = vector<VI>;

ll N, M;
VI mn;   // min?
VI ren;  // renumber table
VV perm; // input

int main()
{
  cin >> N >> M;
  mn.resize(N + 5);
  ren.resize(N + 5);
  perm.resize(15, VI(N + 5));
  ll n = N;
  ll m = M;

  // input
  for (int i = 1; i <= m; ++i)
    for (int j = 1; j <= n; ++j)
      scanf("%d", &perm[i][j]);

  // renumber table
  for (int i = 1; i <= n; ++i)
    ren[perm[1][i]] = i;

  // renumbered permutation
  for (int i = 1; i <= m; ++i)
    for (int j = 1; j <= n; ++j)
      perm[i][j] = ren[perm[i][j]];

  // iからスタートしてどこまで行けるか。の積集合(min)
  // 例
  // mn[3]=6
  // it means 3,4,5,6
  for (int i = 1; i <= n; ++i)
    mn[i] = n;

  for (int i = 1; i <= m; ++i)
  {
    int cur = 1;
    for (int j = 1; j <= n; ++j)
    {
      if (cur < j)
        ++cur;

      while (cur < n && perm[i][cur + 1] == perm[i][cur] + 1)
        ++cur;
      mn[perm[i][j]] = min(mn[perm[i][j]], perm[i][cur]);
    }
  }

  ll res = 0;
  int now = 1;
  while (now <= n)
  {
    ll cur = mn[now] - now + 1; // 長さ
    res += (cur + 1) * cur / 2; // nC2
    now = mn[now] + 1;          // 次の連続点までジャンプ
  }

  p(res);
  return 0;
}