• D - Cross Explosion
  • Problem Statement
• E - Avoid K Partition
  • Problem Statement

D - Cross Explosion

Problem Statement

There is a grid with $H$ rows and $W$ columns. Let $(i, j)$ denote the cell at the $i$-th row from the top and $j$-th column from the left.
Initially, there is one wall in each cell.
After processing $Q$ queries explained below in the order they are given, find the number of remaining walls.

In the $q$-th query, you are given two integers $R_q$ and $C_q$.
You place a bomb at $(R_q, C_q)$ to destroy walls. As a result, the following process occurs.

• If there is a wall at $(R_q, C_q)$, destroy that wall and end the process.
• If there is no wall at $(R_q, C_q)$, destroy the first walls that appear when looking up, down, left, and right from $(R_q, C_q)$. More precisely, the following four processes occur simultaneously:
  • If there exists an $i \lt R_q$ such that a wall exists at $(i, C_q)$ and no wall exists at $(k, C_q)$ for all $i \lt k \lt R_q$, destroy the wall at $(i, C_q)$.
  • If there exists an $i \gt R_q$ such that a wall exists at $(i, C_q)$ and no wall exists at $(k, C_q)$ for all $R_q \lt k \lt i$, destroy the wall at $(i, C_q)$.
  • If there exists a $j \lt C_q$ such that a wall exists at $(R_q, j)$ and no wall exists at $(R_q, k)$ for all $j \lt k \lt C_q$, destroy the wall at $(R_q, j)$.
  • If there exists a $j \gt C_q$ such that a wall exists at $(R_q, j)$ and no wall exists at $(R_q, k)$ for all $C_q \lt k \lt j$, destroy the wall at $(R_q, j)$.

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n, m, q;
    cin >> n >> m >> q;

    vector<set<int>> col(m + 1), lin(n + 1);
    vector<vector<bool>> st(n + 1, vector<bool>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) col[j].insert(i), lin[i].insert(j), st[i][j] = 1;
    int res = n * m;
    while (q--) {
        int x, y;
        cin >> x >> y;

        if (st[x][y]) {
            res--, st[x][y] = 0;
            col[y].erase(x), lin[x].erase(y);
            continue;
        }
        auto up = col[y].upper_bound(x), down = up, left = lin[x].upper_bound(y), right = left;
        if (up != col[y].begin()) {
            up--, res--, st[*up][y] = 0;
            col[y].erase(up), lin[*up].erase(y);
        }
        if (down != col[y].end()) {
            res--, st[*down][y] = 0;
            col[y].erase(down), lin[*down].erase(y);
        }
        if (left != lin[x].begin()) {
            left--, res--, st[x][*left] = 0;
            lin[x].erase(left), col[*left].erase(x);
        }
        if (right != lin[x].end()) {
            res--, st[x][*right] = 0;
            lin[x].erase(right), col[*right].erase(x);
        }
    }

    cout << res << endl;

    return 0;
}

E - Avoid K Partition

Problem Statement

You are given a sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$ and an integer $K$.
There are $2^{N-1}$ ways to divide $A$ into several contiguous subsequences. How many of these divisions have no subsequence whose elements sum to $K$? Find the count modulo $998244353$.

Here, “to divide $A$ into several contiguous subsequences” means the following procedure.

• Freely choose the number $k$ $(1 \leq k \leq N)$ of subsequences and an integer sequence $(i_1, i_2, \dots, i_k, i_{k+1})$ satisfying $1 = i_1 \lt i_2 \lt \dots \lt i_k \lt i_{k+1} = N+1$.
• For each $1 \leq n \leq k$, the $n$-th subsequence is formed by taking the $i_n$-th through $(i_{n+1} - 1)$-th elements of $A$, maintaining their order.

Here are some examples of divisions for $A = (1, 2, 3, 4, 5)$:

• $(1, 2, 3), (4), (5)$
• $(1, 2), (3, 4, 5)$
• $(1, 2, 3, 4, 5)$

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int mod = 998244353;

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n, k;
    cin >> n >> k;

    vector<int> a(n + 1), s(n + 1, 0);
    for (int i = 1; i <= n; i ++)
        cin >> a[i], s[i] = s[i - 1] + a[i];

    vector<int> dp(n + 1, 0);
    unordered_map<int, int> tot;
    dp[0] = 1, tot[0] = 1;
    int sum = 1;
    for (int i = 1; i <= n; i ++) {
        dp[i] = (sum - tot[s[i] - k] + mod) % mod;
        (sum += dp[i]) %= mod, (tot[s[i]] += dp[i]) %= mod;
    }

    cout << dp[n] << endl;

    return 0;
}