| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 282662 | Haunted_Cpp | 자리 배치 (IOI18_seats) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct SegmentTree {
vector<int> mn, mx;
const int n;
SegmentTree(const vector<int> &arr) : n(arr.size()) {
mn = mx = vector<int>(2 * n);
for (int i = 0; i < n; i++) mn[i + n] = mx[i + n] = arr[i];
for (int i = n - 1; i > 0; i--) {
mn[i] = min(mn[i << 1], mn[i << 1 | 1]);
mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
}
}
void modify(int where, int delta) {
where += n;
mn[where] = mx[where] = delta;
for (; delta > 1; delta >>= 1) {
mn[where >> 1] = min(mn[where], mn[where ^ 1]);
mx[where >> 1] = max(mx[where], mx[where ^ 1]);
}
}
pair<int, int> rmq(int l, int r) {
pair<int, int> res = {INF, -INF};
l += n;
r += n;
res.first = min(res.first, mn[l]);
res.first = min(res.first, mn[r]);
res.second = max(res.second, mx[l]);
res.second = max(res.second, mx[r]);
for(; l <= r; l >>= 1, r >>= 1) {
if (l & 1) {
res.first = min(res.first, mn[l]);
res.second = max(res.second, mx[l]);
++l;
}
if (r & 1 ^ 1) {
res.first = min(res.first, mn[r]);
res.second = max(res.second, mx[r]);
--r;
}
}
return res;
}
};
int H, W;
vector<int> R, C;
SegmentTree *rows, *cols;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
::H = H; ::W = W;
::R = R; ::C = C;
rows = new SegmentTree(R);
cols = new SegmentTree(C);
}
int swap_seats(int a, int b) {
swap(R[a], R[b]);
swap(C[a], C[b]);
rows -> modify(a, R[a]);
rows -> modify(b, R[b]);
cols -> modify(a, C[a]);
cols -> modify(b, C[b]);
int idx = 0, res = 0;
while(idx < H * W) {
tie(R_min, R_max) = rows -> query(0, idx);
tie(C_min, C_max) = cols -> query(0, idx);
int score = (R_max - R_min + 1) * (C_max - C_min + 1);
if (score == idx + 1) {
++res;
++idx;
} else {
idx = score - 1;
}
}
return res;
}