Submission #996764

#	Time	Username	Problem	Language	Result	Execution time	Memory
996764		abczz	Misspelling (JOI22_misspelling)	C++17	100 / 100	434 ms	218452 KiB

misspelling

#include <iostream>
#include <vector>
#include <array>
#define ll long long

using namespace std;

ll M = 1e9 + 7;
vector <array<ll, 2>> V[2];
ll n, m, a, b, s, t, f, L[500000], G[500000], dp[500000][26], ps[500000][26];

int main() {
  cin >> n >> m;
  for (int i=0; i<n; ++i) {
    L[i] = G[i] = -2;
  }
  for (int i=0; i<m; ++i) {
    cin >> a >> b;
    --a, --b;
    if (a < b) G[a] = max(G[a], b-1);
    else L[b] = max(L[b], a-1);
  }
  int j=0, k=0;
  for (int i=0; i<n; ++i) {
    for (int q=0; q<2; ++q) {
      while (!V[q].empty()) {
        auto [x, y] = V[q].back();
        if (y < i-1) V[q].pop_back();
        else break;
      }
    }
    a = b = -1;
    if (!V[0].empty()) a = V[0].back()[0];
    if (!V[1].empty()) b = V[1].back()[0];
    if (!i) {
      for (int j=0; j<26; ++j) {
        dp[i][j] = 1;
        ps[i][j] = 1;
      }
    }
    else if (a == -1 && b == -1) {
      s = 0;
      for (int j=0; j<26; ++j) {
        (s += ps[i-1][j]) %= M;
      }
      for (int j=0; j<26; ++j) {
        dp[i][j] = (s - ps[i-1][j] + M) % M;
      }
    }
    else if (a == -1) {
      s = t = 0;
      for (int j=0; j<26; ++j) {
        s = (s + ps[i-1][j] - ps[b][j] + M) % M;
        t = (t + ps[b][j]) % M;
      }
      for (int j=0; j<26; ++j) {
        t = (t-ps[b][j]+M) % M;
        dp[i][j] = (s - ((ps[i-1][j] - ps[b][j] + M) % M) + t + M) % M;
      }
    }
    else if (b == -1) {
      s = t = 0;
      for (int j=0; j<26; ++j) {
        s = (s + ps[i-1][j] - ps[a][j] + M) % M;
        t = (t + ps[a][j]) % M;
      }
      for (int j=25; j>=0; --j) {
        t = (t-ps[a][j]+M) % M;
        dp[i][j] = (s - ((ps[i-1][j] - ps[a][j] + M) % M) + t + M) % M;
      }
    }
    else if (a < b) {
      s = t = 0;
      for (int j=0; j<26; ++j) {
        s = (s + ps[i-1][j] - ps[b][j] + M) % M;
        t = (t + ps[b][j] - ps[a][j] + M) % M;
      }
      for (int j=0; j<26; ++j) {
        t = (t-((ps[b][j] - ps[a][j] + M) % M)+M) % M;
        dp[i][j] = (s - ((ps[i-1][j] - ps[b][j] + M) % M) + t + M) % M;
      }
    }
    else if (a > b) {
      s = t = 0;
      for (int j=0; j<26; ++j) {
        s = (s + ps[i-1][j] - ps[a][j] + M) % M;
        t = (t + ps[a][j] - ps[b][j] + M) % M;
      }
      for (int j=25; j>=0; --j) {
        t = (t-((ps[a][j] - ps[b][j] + M) % M)+M) % M;
        dp[i][j] = (s - ((ps[i-1][j] - ps[a][j] + M) % M) + t + M) % M;
      }
    }
    else {
      s = 0;
      for (int j=0; j<26; ++j) {
        s = (s + ps[i-1][j] - ps[b][j] + M) % M;
      }
      for (int j=0; j<26; ++j) {
        dp[i][j] = (s - ((ps[i-1][j] - ps[b][j] + M) % M) + M) % M;
      }
    }
    if (i) {
      for (int j=0; j<26; ++j) ps[i][j] = (ps[i-1][j] + dp[i][j]) % M;
    }
    while (!V[0].empty()) {
      auto [x, y] = V[0].back();
      if (L[i] >= y) V[0].pop_back();
      else break;
    }
    V[0].push_back({i, L[i]});
    while (!V[1].empty()) {
      auto [x, y] = V[1].back();
      if (G[i] >= y) V[1].pop_back();
      else break;
    }
    V[1].push_back({i, G[i]});
  }
  for (int i=0; i<26; ++i) {
    f += ps[n-1][i];
    f %= M;
  }
  cout << f << '\n';
}

Compilation message (stderr)

misspelling.cpp: In function 'int main()':
misspelling.cpp:23:7: warning: unused variable 'j' [-Wunused-variable]
   23 |   int j=0, k=0;
      |       ^
misspelling.cpp:23:12: warning: unused variable 'k' [-Wunused-variable]
   23 |   int j=0, k=0;
      |            ^

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