제출 #957174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
957174		NeroZein	Misspelling (JOI22_misspelling)	C++17	100 / 100	1808 ms	170156 KiB

misspelling

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

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int A = 26;
const int N = 5e5 + 5;
const int md = (int) 1e9 + 7;

int dp[N][A];
int ps[N][A];
vector<int> smaller[N], bigger[N];

int sub(int a, int b) {
  a -= b;
  if (a < 0) a += md;
  return a; 
}

void add(int& a, int b) {
  a += b;
  if (a >= md) a -= md; 
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    if (a < b) {
      smaller[a].push_back(a);//1
      smaller[b].push_back(-a);//1
    } else {
      bigger[b].push_back(b);//2
      bigger[a].push_back(-b);//2
    }
  }
  for (int i = 0; i < A; ++i) {
    dp[1][i] = 1; 
  }
  vector<multiset<int>> se(3); 
  for (int i = 1; i <= n; ++i) {
    int mx1 = 0, mx2 = 0;
    if (!se[1].empty()) mx1 = max(0, *se[1].rbegin());
    if (!se[2].empty()) mx2 = max(0, *se[2].rbegin());
    int mx = max(mx1, mx2);
    int mn = min(mx1, mx2); 
    for (int j = 0; j < A; ++j) {
      for (int l = 0; l < A; ++l) {
        if (l == j) continue;
        int s = sub(ps[i - 1][l], ps[mx][l]);
        add(dp[i][j], s); 
        int st = (mx1 == mx ? 1 : 0) | (mx2 == mx ? 2 : 0);
        s = sub(ps[mx][l], ps[mn][l]);
        add(dp[i][j], s * (st & 1 ? l < j: 1) * (st & 2 ? l > j : 1)); 
      }
    }
    for (int x : smaller[i]) {
      if (x > 0) se[1].insert(x);
      else se[1].erase(se[1].find(-x)); 
    }
    for (int x : bigger[i]) {
      if (x > 0) se[2].insert(x);
      else se[2].erase(se[2].find(-x)); 
    }
    for (int j = 0; j < A; ++j) {
      ps[i][j] = ps[i - 1][j];
      add(ps[i][j], dp[i][j]);
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < A; ++j) {
      add(ans, dp[i][j]); 
    }
  }
  cout << ans << '\n'; 
  return 0;
}

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