Submission #1139705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139705		dlalswp25	여왕벌 (KOI15_queen)	C++20	100 / 100	1502 ms	280100 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> piii;

int N, Q;
int ans[707][707];
char A[707][707][7];
char buf[30];
int dfn[2][1010101];
int ed[2][1010101];
vector<int> adj[2][1010101];
int D[707][707][6];
int E01[707][707][2];
int E12[707][707][2];
int F[707][707];
int I[707][707][2];
tuple<short, short, char> coord[1010101];
int vid;
vector<int> us[1010101];
vector<int> qs[1010101];
int P[1010101];
pair<short, short> qans[2020202];
pii qv[2020202];

void add(int x1, int y1, int x2, int y2, int v) {
    ans[x1][y1] += v;
    ans[x1][y2 + 1] -= v;
    ans[x2 + 1][y1] -= v;
    ans[x2 + 1][y2 + 1] += v;
}

int id(int x, int y, int z) {
    if (x > N || y > N) return 1;
    return I[x][y][z];
}

void dfs(int t, int v) {
    dfn[t][v] = ++vid;
    for (int i : adj[t][v]) {
        dfs(t, i);
    }
    ed[t][v] = vid;
}

int main() {
    scanf("%d%d", &N, &Q);
    vid = 1;
    for (int i = 2 * N; i >= 2; i--) {
        for (int j = max(1, i - N); j <= min(N, i - 1); j++) {
            for (int k = 0; k < 2; k++) {
                I[j][i - j][k] = ++vid;
                coord[vid] = {j, i - j, k};
            }
        }
    }
    
    add(1, 1, N, N, Q + 1);
    for (int i = 2; i <= N; i++) {
        for (int j = 2; j <= N; j++) {
            scanf("%s", buf);
            auto parse = [&](int idx, int l, int d, int u) {
                char c = buf[9 * l + 3 * d + u];
                A[i][j][idx] = (c == 'L' ? 0 : (c == 'D' ? 1 : 2));
            };
            parse(0, 0, 0, 1); parse(1, 0, 1, 1);
            parse(2, 0, 0, 2); parse(3, 0, 2, 2);
            parse(4, 1, 1, 2); parse(5, 1, 2, 2);
            parse(6, 0, 1, 2);
            for (int k = 0; k < 2; k++) {
                if (A[i][j][k << 2] <= 1) adj[k][id(i, j + 1, 1)].push_back(id(i, j, 0));
                else adj[k][id(i + 1, j, 0)].push_back(id(i, j, 0));
                if (A[i][j][k << 2 | 1] == 0) adj[k][id(i, j + 1, 1)].push_back(id(i, j, 1));
                else adj[k][id(i + 1, j, 0)].push_back(id(i, j, 1));
            }  
        }
    }
    
    for (int i = 0; i < 2; i++) { vid = 0; dfs(i, 1); }
    
    vector<pii> gov;
    while (Q--) {
        int a, b, c; scanf("%d%d%d", &a, &b, &c);
        if (!a + !b + !c >= 2) {
            add(1, 1, N, N, a ? -1 : (b ? 0 : 1));
        } else if (!a + !b + !c == 1) {
            int u, v, x, y, i;
            if (!a) { u = b; v = c; x = 0; y = 1; i = 4; }
            else if (!b) { u = a; v = c; x = -1; y = 1; i = 2; }
            else { u = a; v = b; x = -1; y = 0; i = 0; }
            if (u >= N) {
                add(1, 1, N, u - N + 1, x);
                add(1, u - N + 2, 1, N, y);
                D[2][u - N + 2][i]++;
            } else {
                add(1, 1, v - N + 1, N, y);
                add(v - N + 2, 1, N, 1, x);
                D[v - N + 2][2][i + 1]++;
            }
        } else if (a == c && b == 1) {
            add(2, 1, N, 1, -1);
            add(1, 2, 1, N, 1);
            F[2][2]++;
        } else {
            int x1, y1, z1, x2, y2, z2;
            if (a >= N) {
                add(1, 1, N, a - N + 1, -1);
                x1 = 2; y1 = a - N + 2; z1 = 0;
            } else {
                add(N - a + 1, 1, N, 1, -1);
                x1 = N - a + 1; y1 = 2; z1 = 1;
            }
            if (c >= N) {
                add(1, 1, c - N + 1, N, 1);
                x2 = c - N + 2; y2 = 2; z2 = 1;
            } else {
                add(1, N - c + 1, 1, N, 1);
                x2 = 2; y2 = N - c + 1; z2 = 0;
            }
            int p1 = id(x1, y1, z1), p2 = id(x2, y2, z2);
            qs[dfn[0][p1]].push_back(dfn[1][p2]);
            gov.emplace_back(p1, p2);
        }
    }

    for (int i = 2; i < N; i++) {
        for (int j = 2; j < N; j++) {
            qs[dfn[0][id(i + 1, j, 0)]].push_back(dfn[1][id(i, j + 1, 1)]);
        }
    }

    for (int i = 2; i <= N; i++) {
        for (int j = 2; j <= N; j++) {
            int u = id(i, j, 1), v = id(i, j, 0);
            us[dfn[0][u]].push_back(v);
            us[ed[0][u] + 1].push_back(-v);
        }
    }

    int M = 2 * N * N + 1;
    set<pii> S;

    auto query = [&](int x) {
        auto it = S.lower_bound({x + 1, -1010101010});
        if (it == S.begin()) return 0;
        return abs((--it)->second);
    };

    int qn = 0;
    for (int i = 1; i <= M; i++) {
        for (int v : us[i]) {
            bool add = (v > 0); v = abs(v);
            int l = dfn[1][v], r = ed[1][v];
            if (add) {
                int t = query(l);
                if (t < v) {
                    S.emplace(l, v);
                    S.emplace(r + 1, -t);
                    P[v] = t;
                }
            } else {
                auto it = S.find({l, v});
                if (it != S.end()) S.erase(it);
                it = S.find({r + 1, -P[v]});
                if (it != S.end()) S.erase(it);
            }
        }
        sort(qs[i].begin(), qs[i].end());
        for (int j : qs[i]) {
            auto [x, y, _] = coord[query(j)];
            qans[qn] = {x, y};
            qv[qn++] = {i, j};
        }
        vector<int>().swap(us[i]);
        vector<int>().swap(qs[i]);
    }

    auto go = [&](int p1, int p2, int c) {
        auto [x1, y1, z1] = coord[p1];
        auto [x2, y2, z2] = coord[p2];
        int qi = lower_bound(qv, qv + qn, pii(dfn[0][p1], dfn[1][p2])) - qv;
        auto [x, y] = qans[qi];
        E01[x1][y1][z1] += c; E12[x2][y2][z2] += c;
        if (x) {
            E01[x][y][1] -= c; E12[x][y][0] -= c;
            F[x][y] += c;
        }
    };

    for (auto [p1, p2] : gov) go(p1, p2, 1);

    for (int i = 2; i <= N; i++) {
        for (int j = 2; j <= N; j++) {
            // D
            for (int k = 0; k < 6; k++) {
                int c = D[i][j][k];
                if ((k % 2 == 0 && A[i][j][k] <= 1) || (k % 2 == 1 && A[i][j][k] == 0)) {
                    D[i][j + 1][k | 1] += c;
                    if (k < 4) add(i, j, N, j, -c);
                } else {
                    D[i + 1][j][k & ~1] += c;
                    if (k > 1) add(i, j, i, N, c);
                }
            }
            // E01
            for (int k = 0; k < 2; k++) {
                int c = E01[i][j][k];
                int r = ((!k && A[i][j][k] <= 1) || (k && !A[i][j][k]));
                if (r) {
                    E01[i][j + 1][1] += c;
                    add(i, j, N, j, -c);
                } else {
                    E01[i + 1][j][0] += c;
                }
            }
            // E12
            for (int k = 0; k < 2; k++) {
                int c = E12[i][j][k];
                int r = ((!k && A[i][j][4 | k] <= 1) || (k && !A[i][j][4 | k]));
                if (r) {
                    E12[i][j + 1][1] += c;
                } else {
                    E12[i + 1][j][0] += c;
                    add(i, j, i, N, c);
                }
            }
            // F
            int c = F[i][j];
            if (!c) continue;
            if (!A[i][j][6]) {
                D[i][j + 1][3] += c;
                add(i, j, N, j, -c);
            } else if (A[i][j][6] == 2) {
                D[i + 1][j][2] += c;
                add(i, j, i, N, c);
            } else if (i == N) {
                D[i][j + 1][5] += c;
            } else if (j == N) {
                D[i + 1][j][0] += c;
            } else {
                go(id(i + 1, j, 0), id(i, j + 1, 1), c);
            }
        }
    }
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            ans[i][j] += ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1];
            printf("%d ", ans[i][j]);
        }
        puts("");
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d%d", &N, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:62:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |             scanf("%s", buf);
      |             ~~~~~^~~~~~~~~~~
Main.cpp:84:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         int a, b, c; scanf("%d%d%d", &a, &b, &c);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 34 / 34
• Subtask 4: 32 / 32