제출 #894235

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
894235		box	Misspelling (JOI22_misspelling)	C++17	100 / 100	2383 ms	261676 KiB

misspelling

#include "bits/stdc++.h"
using namespace std;
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
 
#define ar array
#define all(v) (v).begin(), (v).end()
#define sz(v) static_cast<int>(v.size())
typedef vector<int> vi;
typedef long long ll;
 
const int N = 5e5, N_ = 1 << 19, MD = 1e9 + 7;
 
struct ST {
  ar<int, 26> t[N_ * 2];
  bool on[N_ * 2];
 
  void bld(int k, int l, int r) {
    fill(all(t[k]), 0);
    on[k] = 1;
    if (l < r) {
      int m = (l + r) / 2;
      bld(k << 1 | 0, l, m), bld(k << 1 | 1, m + 1, r);
    }
  }
  void upd(int k, int l, int r, int i, ar<int, 26>& x) {
    F0R(c, 26)
    t[k][c] = (t[k][c] + x[c]) % MD;
    if (l < r) {
      int m = (l + r) / 2;
      if (i <= m)
        upd(k << 1 | 0, l, m, i, x);
      else
        upd(k << 1 | 1, m + 1, r, i, x);
    }
  }
  void clr(int k, int l, int r, int ql, int qr) {
    if (!on[k] || ql > r || qr < l) return;
    if (ql <= l && qr >= r) {
      if (l < r) {
        int m = (l + r) / 2;
        clr(k << 1 | 0, l, m, ql, qr);
        clr(k << 1 | 1, m + 1, r, ql, qr);
      }
      fill(all(t[k]), 0);
      on[k] = 0;
      return;
    }
    int m = (l + r) / 2;
    clr(k << 1 | 0, l, m, ql, qr);
    clr(k << 1 | 1, m + 1, r, ql, qr);
    F0R(c, 26) t[k][c] = (t[k << 1 | 0][c] + t[k << 1 | 1][c]) % MD;
  }
  ar<int, 26>& root() { return t[1]; }
} t1, t2;
 
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin.exceptions(cin.failbit);
  int n, m;
  cin >> n >> m;
  static vi v1[N], v2[N];
  F0R(h, m) {
    int l, r;
    cin >> l >> r, l--, r--;
    if (l < r)
      v1[l].push_back(r);  // s_i > s_{i+1}
    else
      v2[r].push_back(l);  // s_i < s_{i+1}
  }
  t1.bld(1, 0, n - 1);
  t2.bld(1, 0, n - 1);
  ar<int, 26> dp;
  R0F(i, n) {
    if (i == n - 1)
      fill(all(dp), 1);
    else {
      for (int j : v1[i]) t1.clr(1, 0, n - 1, i + 1, j);
      for (int j : v2[i]) t2.clr(1, 0, n - 1, i + 1, j);
      F0R(c, 26) {
        dp[c] = 1;
        FOR(b, 0, c) dp[c] = (dp[c] + t1.root()[b]) % MD;
        FOR(b, c + 1, 26) dp[c] = (dp[c] + t2.root()[b]) % MD;
      }
    }
    t1.upd(1, 0, n - 1, i, dp);
    t2.upd(1, 0, n - 1, i, dp);
  }
  int ans = 0;
  F0R(c, 26) ans = (ans + dp[c]) % MD;
  cout << ans << '\n';
}

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