제출 #1038966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038966		juicy	Misspelling (JOI22_misspelling)	C++17	100 / 100	310 ms	64240 KiB

misspelling

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 5e5 + 5, C = 26, MD = 1e9 + 7;

void add(int &x, int y) {
  if ((x += y) >= MD) {
    x -= MD;
  }
  if (x < 0) {
    x += MD;
  }
}

int n, m;
int dp[N][C], cur[2][C];
vector<int> st[2];

void pop(int i, int x) {
  while (st[i].size() && st[i].back() <= x) {
    for (int j = 0; j < C; ++j) {
      add(cur[i][j], -dp[st[i].back()][j]);
    }
    st[i].pop_back();
  }
}

void psh(int i) {
  st[0].push_back(i);
  st[1].push_back(i);
  for (int j = 0; j < C; ++j) {
    for (auto it : {0, 1}) {
      add(cur[it][j], dp[i][j]);
    }
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> m;
  vector<array<int, 3>> events;
  for (int i = 1; i <= m; ++i) {
    int a, b; cin >> a >> b;
    if (a < b) {
      events.push_back({a + 1, b, 1});
    } else {
      events.push_back({b + 1, a, 0});
    }
  }
  fill(dp[n], dp[n] + C, 1);
  psh(n);
  sort(events.rbegin(), events.rend());
  for (int i = n - 1, j = 0; i > 0; --i) {
    while (j < m && events[j][0] > i) {
      pop(events[j][2], events[j][1]);
      ++j;
    }
    int sum = 1;
    for (int j = 0; j < C; ++j) {
      dp[i][j] = sum;
      add(sum, cur[0][j]);
    }
    sum = 0;
    for (int j = C - 1; j >= 0; --j) {
      add(dp[i][j], sum);
      add(sum, cur[1][j]);
    }
    psh(i);
  }
  int res = 0;
  for (int i = 0; i < C; ++i) {
    add(res, dp[1][i]);
  }
  cout << res;
  return 0;
}

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