Submission #70469688

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <numeric>
#include <stack>
#include <cassert>
#include <cstring>
#include <cmath>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <chrono>
#include <sstream>
#include <limits>
#include <functional>
using namespace std;
#define endl '\n'
// #define LOCAL

using int64 = int64_t;
using uint64 = unsigned long long;
using int128 = __int128_t;

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

using Matrix3 = array<array<int, 3>, 3>;

const int INF = numeric_limits<int>::max();
int N, Q;
Matrix3 bases[9] = {
    {{{0, 1, 2}, {1, 0, 1}, {2, 1, 0}}},
    {{{INF, INF, INF}, {INF, 0, 1}, {INF, 1, 0}}},
    {{{0, INF, INF}, {INF, INF, INF}, {INF, INF, 0}}},
    {{{INF, INF, INF}, {INF, INF, INF}, {INF, INF, 0}}},
    {{{0, 1, INF}, {1, 0, INF}, {INF, INF, INF}}},
    {{{INF, INF, INF}, {INF, 0, INF}, {INF, INF, INF}}},
    {{{0, INF, INF}, {INF, INF, INF}, {INF, INF, INF}}},
    {{{INF, INF, INF}, {INF, INF, INF}, {INF, INF, INF}}},
    {{{-1, -1, -1}, {-1, -1, -1}, {-1, -1, -1}}} // blocked
};
vector<string> grid;
vector<int> colMasks;

template<class Node>
struct SegmentTree {
    struct Configuration {
        const Node neutral;                           // identity for merge
        function<Node(const Node&, const Node&)> merge;           // combine two nodes
    } config;

    int size = 0;
    vector<Node> nodes;

    SegmentTree(int n, Configuration config) : config(config) { init(n); }

    void init(int num_nodes) {
        size = 1;
        while (size < num_nodes) size *= 2;
        nodes.assign(size * 2, config.neutral);
    }

    // this is for assign, for addition change to += val
    void update(int segment_idx, const Node& val) {
        segment_idx += size;
        nodes[segment_idx] = val; // += val if want addition, to track frequency
        for (segment_idx >>= 1; segment_idx >= 1; segment_idx >>= 1) pull(segment_idx);
    }

    Node query(int left, int right) {
        left += size, right += size;
        Node left_acc = config.neutral;
        Node right_acc = config.neutral;
        while (left <= right) {
           if (left & 1) {
                // res on left
                left_acc = config.merge(left_acc, nodes[left++]);
            }
            if (~right & 1) {
                // res on right
                right_acc = config.merge(nodes[right--], right_acc);
            }
            left >>= 1, right >>= 1;
        }
        return config.merge(left_acc, right_acc);
    }
    private:
        inline void pull(int segment_idx) { nodes[segment_idx] = config.merge(nodes[segment_idx << 1], nodes[segment_idx << 1 | 1]); }
};

SegmentTree<Matrix3>::Configuration cfg{
    /*neutral*/ bases[8],
    /*merge*/   [](const Matrix3 &X, const Matrix3 &Y) {
        Matrix3 Z;
        if (X[0][0] == -1) return Y;
        if (Y[0][0] == -1) return X;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                Z[i][j] = INF;
                for (int k = 0; k < 3; ++k) {
                    if (X[i][k] != INF && Y[k][j] != INF)
                        Z[i][j] = min(Z[i][j], X[i][k] + Y[k][j]);
                }   
            }
        }
        return Z;
    }
};

void solve() {
    cin >> N;
    grid.resize(3);
    colMasks.assign(N, 0);
    for (int i = 0; i < 3; i++) {
        cin >> grid[i];
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (grid[j][i] == '#') colMasks[i] |= (1 << j);
        }
    }
    SegmentTree<Matrix3> seg(N, cfg);
    for (int i = 0; i < N; ++i) {
        seg.update(i, bases[colMasks[i]]);
    }
    cin >> Q;
    while (Q--) {
        int r, c;
        cin >> r >> c;
        r--, c--;
        colMasks[c] ^= (1 << r);
        seg.update(c, bases[colMasks[c]]);
        Matrix3 mat = seg.nodes[1];
        int ans = mat[0][2] != INF ? mat[0][2] + N - 1 : -1;
        cout << ans << endl;
    }
}

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

Submission Info

Judge Result