Submission #1169667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169667		fryingduc	Misspelling (JOI22_misspelling)	C++20	100 / 100	315 ms	105876 KiB

misspelling

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 5e5 + 5;
const int mod = 1e9 + 7;
int n, m, a[maxn], b[maxn];
int f[maxn][26], g[2][26];
vector<pair<int, int>> ev[maxn];
set<int> st[2];

int add(int x, int y) {
  if (y < 0) y += mod;
  x = x + y;
  if (x >= mod) x -= mod;
  return x;
}

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int x, y; cin >> x >> y;
    if (x < y) {
      ev[x + 1].emplace_back(y, 1);
    } else {
      ev[y + 1].emplace_back(x, 0);
    }
  }
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j < 26; ++j) {
      f[i][j] = 1;
    }
  }
  auto ins = [&](int p) {
    st[0].insert(p);
    st[1].insert(p);
    for (int i = 0; i < 26; ++i) {
      g[0][i] = add(g[0][i], f[p][i]);
      g[1][i] = add(g[1][i], f[p][i]);
    }
  };
  auto del = [&](int id, int p) {
    while (!st[id].empty() and *st[id].begin() <= p) {
      for (int j = 0; j < 26; ++j) {
        g[id][j] = add(g[id][j], -f[*st[id].begin()][j]);
      }
      st[id].erase(st[id].begin());
    }
  };
  ins(n);
  for (int i = n - 1; i; --i) {
    for (auto [p, id] : ev[i + 1]) {
      del(id, p);
    }
    int sum = 1;
    for (int j = 0; j < 26; ++j) {
      f[i][j] = sum;
      sum = add(sum, g[0][j]);
    }
    sum = 0;
    for (int j = 25; j >= 0; --j) {
      f[i][j] = add(f[i][j], sum);
      sum = add(sum, g[1][j]);
    }
    ins(i);
  } 
  int res = 0;
  for (int j = 0; j < 26; ++j) {
    res = add(res, f[1][j]);
  }
  cout << res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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