Submission #1178522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178522		tch1cherin	Misspelling (JOI22_misspelling)	C++20	100 / 100	1302 ms	282148 KiB

misspelling

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

constexpr int MOD = 1e9 + 7;
constexpr int ALPHA = 26;

int add(int a, int b) {
  return a + b < MOD ? a + b : a + b - MOD;
}

int sub(int a, int b) {
  return a - b < 0 ? a - b + MOD : a - b;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<int> A(M), B(M);
  for (int i = 0; i < M; i++) {
    cin >> A[i] >> B[i];
    --A[i], --B[i];
  }
  vector<vector<int>> gt(N), lt(N);
  for (int i = 0; i < M; i++) {
    if (A[i] == B[i]) {
      continue;
    }
    if (A[i] < B[i]) {
      gt[A[i]].push_back(B[i]);
    } else {
      lt[B[i]].push_back(A[i]);
    }
  }
  vector DP(N, vector<int>(ALPHA));
  vector pref(N + 1, vector<int>(ALPHA + 1)), suff(N + 1, vector<int>(ALPHA + 1));
  DP[0].assign(ALPHA, 1);
  set<array<int, 2>> lt_left, lt_right, gt_left, gt_right;
  for (int i = 0; i < N; i++) {
    while (!lt_right.empty() && (*lt_right.begin())[0] < i) {
      auto [r, l] = *lt_right.begin();
      lt_right.erase(lt_right.begin());
      lt_left.erase({l, r});
    }
    while (!gt_right.empty() && (*gt_right.begin())[0] < i) {
      auto [r, l] = *gt_right.begin();
      gt_right.erase(gt_right.begin());
      gt_left.erase({l, r});
    }
    int X = 1 + (lt_left.empty() ? -1 : (*lt_left.rbegin())[0]);
    int Y = 1 + (gt_left.empty() ? -1 : (*gt_left.rbegin())[0]);
    for (int ch = 0; ch < ALPHA; ch++) {
      DP[i][ch] = add(DP[i][ch], sub(pref[i][ch], pref[max(X, Y)][ch]));
      DP[i][ch] = add(DP[i][ch], sub(suff[i][ch + 1], suff[max(X, Y)][ch + 1]));
      if (X < Y) {
        DP[i][ch] = add(DP[i][ch], sub(pref[Y][ch], pref[X][ch]));
      } else {
        DP[i][ch] = add(DP[i][ch], sub(suff[X][ch + 1], suff[Y][ch + 1]));
      }
    }
    for (int ch = ALPHA - 1; ch >= 0; ch--) {
      suff[i + 1][ch] = add(suff[i + 1][ch + 1], add(sub(suff[i][ch], suff[i][ch + 1]), DP[i][ch]));
    }
    for (int ch = 0; ch < ALPHA; ch++) {
      pref[i + 1][ch + 1] = add(pref[i + 1][ch], add(sub(pref[i][ch + 1], pref[i][ch]), DP[i][ch]));
    }
    for (int j : lt[i]) {
      lt_left.insert({i, j});
      lt_right.insert({j, i});
    }
    for (int j : gt[i]) {
      gt_left.insert({i, j});
      gt_right.insert({j, i});
    }
  }
  cout << pref[N][ALPHA] << "\n";
}

• Subtask 1: 8 / 8
• Subtask 2: 20 / 20
• Subtask 3: 29 / 29
• Subtask 4: 32 / 32
• Subtask 5: 11 / 11