제출 #1343351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1343351		altern23	Misspelling (JOI22_misspelling)	C++20	8 / 100	433 ms	290056 KiB

misspelling

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

#define ll long long

const int MAXN = 5e5;
const int MOD = 1e9+7;

ll A[MAXN+5], B[MAXN+5];
ll dp[MAXN+5][26], ps[MAXN+5][26];

int main() {
      ios_base::sync_with_stdio(0); cin.tie(0);
      int tc = 1;
      // cin >> tc;
      while (tc--) {
            ll N, M; cin >> N >> M;

            vector <ll> in[N+5][2], out[N+5][2];

            for (int i = 1; i <= M; i++) {
                  cin >> A[i] >> B[i];
                  if (A[i] < B[i]) {
                        // S[A[i]...B[i]-1]] >= S[A[i]+1...B[i]]
                        in[A[i]+1][0].push_back(A[i]+1);
                        out[B[i]][0].push_back(A[i]+1);
                  }
                  else {
                        swap(A[i], B[i]);
                        // S[A[i]...B[i]-1]] <= S[A[i]+1...B[i]]
                        in[A[i]+1][1].push_back(A[i]+1);
                        out[B[i]][1].push_back(A[i]+1);
                  }
            }

            multiset <ll> ms[2];

            auto query = [&](ll l, ll r, ll x, ll y) {
                  if (r < l || y < x) return 0LL;
                  return ps[r][y]-(x == 0 ? 0LL : ps[r][x-1])-ps[l-1][y]+(x == 0 ? 0LL : ps[l-1][x-1]);
            };

            ll ans = 0;

            for (int i = 1; i <= N; i++) {
                  for (int j = 0; j < 2; j++) {
                        for (auto x : in[i][j]) {
                              ms[j].insert(x);
                        }
                  }

                  if (i == 1) {
                        for (int j = 0; j < 26; j++) {
                              dp[i][j] = 1;
                        }
                  }
                  else {
                        for (int j = 0; j < 26; j++) {
                              ll x = (ms[0].empty() ? 1LL : *ms[0].rbegin());
                              ll y = (ms[1].empty() ? 1LL : *ms[1].rbegin());
                              dp[i][j] += query(max(x, y), i-1, 0, 25) - query(max(x, y), i-1, j, j) + MOD;
                              dp[i][j] %= MOD;
                              if (x != y) {
                                    if (x < y) {
                                          dp[i][j] += query(x, y-1, 0, j-1);
                                          dp[i][j] %= MOD;
                                    }
                                    else {
                                          dp[i][j] += query(y, x-1, j+1, 25);
                                          dp[i][j] %= MOD;
                                    }
                              }
                        }
                  }

                  for (int j = 0; j < 26; j++) {
                        ps[i][j] = ps[i-1][j]+(j == 0 ? 0LL : ps[i][j-1])-(j == 0 ? 0LL : ps[i-1][j-1])+dp[i][j];
                        ps[i][j] %= MOD;
                  }

                  for (int j = 0; j < 2; j++) {
                        for (auto x : out[i][j]) {
                              ms[j].erase(ms[j].find(x));
                        }
                  }
            }

            for (int i = 1; i <= N; i++) {
                  for (int j = 0; j < 26; j++) {
                        ans += dp[i][j];
                        ans %= MOD;
                  }
            }

            cout << ans << "\n";
      }
}

/*

*/

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