이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// #include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define i32 int32_t
void give_initial_chart(i32 H, i32 W, vector<i32> R, vector<i32> C);
i32 swap_seats(i32 a, i32 b);
struct Node {
int val, freq;
Node operator + (Node& o) {
if (val == o.val) return {val, freq + o.freq};
if (val < o.val) return {val, freq};
if (val > o.val) return {o.val, o.freq};
}
};
const int inf = 1e9;
struct SegTree {
int size = 1;
vector<Node> seg;
vector<int> lazy;
void init(int n) {
while (size < n) size *= 2;
seg.resize(2 * size + 10);
lazy.assign(2 * size + 10, 0);
}
void build(int l, int r, int id) {
if (l == r) {
seg[id] = {inf, 1};
return;
}
int mid = (l + r) / 2;
build(l, mid, id * 2);
build(mid + 1, r, id * 2 + 1);
seg[id] = seg[id * 2] + seg[id * 2 + 1];
}
void push(int id) {
seg[id].val += lazy[id];
if (id < size) {
for (int i = 0; i < 2; i++) {
lazy[id * 2 + i] += lazy[id];
}
}
lazy[id] = 0;
}
void update(int ql, int qr, int tos, int l, int r, int id) {
push(id);
if (ql <= l && r <= qr) {
lazy[id] += tos;
push(id);
return;
}
if (qr < l || r < ql) return;
int mid = (l + r) / 2;
update(ql, qr, tos, l, mid, id * 2);
update(ql, qr, tos, mid + 1, r, id * 2 + 1);
seg[id] = seg[id * 2] + seg[id * 2 + 1];
}
int query() {
return seg[1].val == 4 ? seg[1].freq : 0;
}
} st;
int n, h, w;
vector<int> rr, cc;
vector<vector<int>> g;
int I(int i, int j) {
return i * w + j + 1;
}
void give_initial_chart(i32 H, i32 W, vector<i32> R, vector<i32> C) {
h = H, w = W, n = h * w;
st.init(n + 1);
g = vector<vector<int>> (h + 2, vector<int> (w + 2, 0));
rr.resize(n), cc.resize(n);
for (int i = 0; i < n; i++) {
g[R[i] + 1][C[i] + 1] = i;
rr[i] = R[i] + 1, cc[i] = C[i] + 1;
}
for (int i = 0; i <= h; i++) {
for (int j = 0; j <= w; j++) {
vector<int> tmp;
tmp.push_back(g[i][j]);
tmp.push_back(g[i][j+1]);
tmp.push_back(g[i+1][j]);
tmp.push_back(g[i+1][j+1]);
sort(tmp.begin(), tmp.end());
st.update(tmp[0], tmp[1] - 1, 1, 1, n, 1);
st.update(tmp[2], tmp[3] - 1, 1e9, 1, n, 1);
}
}
}
i32 swap_seats(i32 a, i32 b) {
vector<pair<int, int>> e;
for (int i = 0; i <= 1; i++) for (int j = 0; j <= 1; j++) {
e.push_back({rr[a] - i, cc[a] - j});
e.push_back({rr[b] - i, cc[b] - j});
}
sort(e.begin(), e.end());
e.erase(unique(e.begin(), e.end()), e.end());
for (auto& [i, j] : e) {
vector<int> tmp;
tmp.push_back(g[i][j]);
tmp.push_back(g[i][j+1]);
tmp.push_back(g[i+1][j]);
tmp.push_back(g[i+1][j+1]);
sort(tmp.begin(), tmp.end());
st.update(tmp[0], tmp[1] - 1, 1, 1, n, 1);
st.update(tmp[2], tmp[3] - 1, 1e9, 1, n, 1);
}
swap(rr[a], rr[b]);
swap(cc[a], cc[b]);
swap(g[rr[a]][cc[a]], g[rr[b]][cc[b]]);
for (auto& [i, j] : e) {
vector<int> tmp;
tmp.push_back(g[i][j]);
tmp.push_back(g[i][j+1]);
tmp.push_back(g[i+1][j]);
tmp.push_back(g[i+1][j+1]);
sort(tmp.begin(), tmp.end());
st.update(tmp[0], tmp[1] - 1, 1, 1, n, 1);
st.update(tmp[2], tmp[3] - 1, 1e9, 1, n, 1);
}
i32 ans = st.query();
return ans;
}
#ifndef EVAL
#include <cstdio>
#include <cstdlib>
#include <vector>
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
int H = read_int();
int W = read_int();
int Q = read_int();
std::vector<int> R(H * W), C(H * W);
for (int i = 0; i < H * W; ++i) {
R[i] = read_int();
C[i] = read_int();
}
std::vector<int> A(Q), B(Q);
for (int j = 0; j < Q; ++j) {
A[j] = read_int();
B[j] = read_int();
}
give_initial_chart(H, W, R, C);
for (int j = 0; j < Q; ++j) {
int answer = swap_seats(A[j], B[j]);
printf("%d\n", answer);
}
return 0;
}
#endif
컴파일 시 표준 에러 (stderr) 메시지
seats.cpp: In member function 'Node Node::operator+(Node&)':
seats.cpp:16:5: warning: control reaches end of non-void function [-Wreturn-type]
16 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |