Submission #1139663

#TimeUsernameProblemLanguageResultExecution timeMemory
1139663dlalswp25여왕벌 (KOI15_queen)C++20
100 / 100
2593 ms340696 KiB
#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]; piii coord[1010101]; int vid; vector<int> us[1010101]; set<int> qs[1010101]; int P[1010101]; pii 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]].insert(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)]].insert(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); } } for (int j : qs[i]) { auto [x, y, _] = coord[query(j)]; qans[qn] = {x, y}; qv[qn++] = {i, j}; } } 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);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...