Submission #1256100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256100		LucaLucaM	Misspelling (JOI22_misspelling)	C++20	100 / 100	1711 ms	147316 KiB

misspelling

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

const int mod = 1e9 + 7;
const int MAXN = 200;
const int SIGMA = 26;

struct DSU {
  std::vector<int> p;
  void init(int n) {
    p.resize(n + 3);
    for (int i = 0; i < n + 3; i++) {
      p[i] = i;
    }
  }
  bool is(int u) {
    return p[u] != u;
  }
  int root(int u) {
    return p[u] == u? u : p[u] = root(p[u]);
  }
  void mark(int u) {
    p[u] = u + 1;
  }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
 
  int n, m;
  std::cin >> n >> m;

  std::vector<std::vector<int>> gpos(n + 2), gneg(n + 2);
  
  for (int i = 0; i < m; i++) {
    int a, b;
    std::cin >> a >> b;
    if (a < b) {
      gneg[a + 1].push_back(b);
    } else if (b < a) {
      gpos[b + 1].push_back(a);
    }
  }

  DSU positive;
  DSU negative;

  positive.init(n);
  negative.init(n);

  std::vector<std::vector<int>> contrib(SIGMA, std::vector<int>(n + 2, 0)); // contrib[x][0] = sum{contrib[x][*]}
  std::vector<std::vector<int>> dp(SIGMA, std::vector<int>(n + 2, 0)); // contrib[x][0] = sum{contrib[x][*]}

  auto refreshSum = [&](int u) {
    bool isPositive = positive.is(u);
    bool isNegative = negative.is(u);
    for (int x = 0; x < SIGMA; x++) {
      contrib[x][0] -= contrib[x][u];
      contrib[x][0] += mod;
      contrib[x][0] %= mod;
      contrib[x][u] = 0;
      if (isPositive && isNegative) {
        contrib[x][u] = 0;
      } else if (isNegative) {
        for (int y = 0; y < x; y++) {
          contrib[x][u] += dp[y][u];
            contrib[x][u] %= mod;
        }
      } else if (isPositive) {
        for (int y = x + 1; y < SIGMA; y++) {
          contrib[x][u] += dp[y][u];
            contrib[x][u] %= mod;
        }
      } else {
        for (int y = 0; y < SIGMA; y++) {
          if (x != y) {
            contrib[x][u] += dp[y][u];
            contrib[x][u] %= mod;
          }
        }
      }
      contrib[x][0] += contrib[x][u];
      contrib[x][0] %= mod;
    }
  };
  
  auto markPositive = [&](int l, int r) {
    int u = positive.root(l);
    while (u <= r) {
      positive.mark(u);
      refreshSum(u);
      u = positive.root(u);
    } 
  };
  auto markNegative = [&](int l, int r) {
    int u = negative.root(l);
    while (u <= r) {
      negative.mark(u);
      refreshSum(u);
      u = negative.root(u);
    }
  };

  for (int i = n; i > 0; i--) {
    for (int j : gpos[i + 1]) {
      markPositive(i + 1, j);
    }
    for (int j : gneg[i + 1]) {
      markNegative(i + 1, j);
    }
    for (int x = 0; x < SIGMA; x++) {
      dp[x][i] = (1 + contrib[x][0]) % mod;
    }
    refreshSum(i);
  }

  ll answer = 0;
  for (int i = 0; i < SIGMA; i++) {
    answer += dp[i][1];
  }
  std::cout << answer % mod;
  
  return 0;
}

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