제출 #957172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
957172		NeroZein	Misspelling (JOI22_misspelling)	C++17	28 / 100	4082 ms	87512 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];
vector<int> smaller[N], bigger[N];

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) {
        for (int k = mx + 1; k < i; ++k) {
          if (l != j) {
            add(dp[i][j], dp[k][l]);            
          }
        }
        int st = (mx1 == mx ? 1 : 0) | (mx2 == mx ? 2 : 0);
        for (int k = mn + 1; k <= mx; ++k) {
          add(dp[i][j], dp[k][l] * (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)); 
    }
  }
  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: 0 / 29
• Subtask 4: 0 / 32
• Subtask 5: 0 / 11