이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 1000000;
struct segtree {
segtree *left, *right;
int mini, count, lazy;
void apply(int x) {
lazy += x, mini += x;
}
void push() {
if (lazy != 0) {
left->apply(lazy);
right->apply(lazy);
lazy = 0;
}
}
void pull() {
mini = min(left->mini, right->mini);
count = 0;
if (left->mini == mini) {
count += left->count;
}
if (right->mini == mini) {
count += right->count;
}
}
segtree(int l, int r) {
lazy = 0;
if (l == r) {
mini = 0, count = 1;
} else {
int m = (l + r) / 2;
left = new segtree(l, m);
right = new segtree(m + 1, r);
pull();
}
}
void update(int a, int b, int x, int l, int r) {
if (a > b || b < l || r < a) {
return;
} else if (a <= l && r <= b) {
apply(x);
} else {
push();
int m = (l + r) / 2;
left->update(a, b, x, l, m);
right->update(a, b, x, m + 1, r);
pull();
}
}
};
array<int, 2> pos[N];
vector<int> seats[N];
segtree *mini;
int n, m;
void update(int i, int j, int x) {
vector<int> in;
for (int r = max(0, i - 1); r <= min(n - 1, i); ++r) {
for (int c = max(0, j - 1); c <= min(m - 1, j); ++c) {
in.push_back(seats[r][c]);
}
}
sort(in.begin(), in.end());
mini->update(in[0], (in.size() == 1 ? n * m : in[1]) - 1, x, 0, n * m - 1);
if (in.size() == 4) {
mini->update(in[2], in[3] - 1, 4 * x, 0, n * m - 1);
}
}
void give_initial_chart(int n, int m, vector<int> r, vector<int> c) {
::n = n, ::m = m;
fill(seats, seats + n, vector<int>(m));
for (int i = 0; i < n * m; ++i) {
seats[r[i]][c[i]] = i;
pos[i] = {r[i], c[i]};
}
mini = new segtree(0, n * m - 1);
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
update(i, j, 1);
}
}
}
int swap_seats(int a, int b) {
vector<array<int, 2>> cells;
for (auto k : {a, b}) {
auto [i, j] = pos[k];
for (auto ki : {0, 1}) {
for (auto kj : {0, 1}) {
cells.push_back({i + ki, j + kj});
}
}
}
sort(cells.begin(), cells.end());
cells.erase(unique(cells.begin(), cells.end()), cells.end());
for (auto [i, j] : cells) {
update(i, j, -1);
}
swap(seats[pos[a][0]][pos[a][1]], seats[pos[b][0]][pos[b][1]]);
swap(pos[a], pos[b]);
for (auto [i, j] : cells) {
update(i, j, 1);
}
return mini->count;
}
# | 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... |