| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 276635 | Haunted_Cpp | Seats (IOI18_seats) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int H, W;
vector<int> R, C;
int LO = 0;
int HI = 0;
struct Node {
int R_min, R_max;
int C_min, C_max;
Node() {
R_min = C_min = INF;
R_max = C_max = -INF;
}
void merge(Node l, Node r) {
R_min = min(l.R_min, r.R_min);
C_min = min(l.C_min, r.C_min);
R_max = max(l.R_max, r.R_max);
C_max = max(l.C_max, r.C_max);
}
};
struct SegmentTree {
vector<Node> seg;
SegmentTree() {
seg.resize(4 * R.size());
build(LO, HI - 1, 0, R, C);
}
void build(int l, int r, int node) {
if (l == r) {
seg[node].R_min = seg[node].R_max = R[l];
seg[node].C_min = seg[node].C_max = C[l];
return;
}
int mid = l + (r - l) / 2;
build(l, mid, 2 * node + 1, R, C);
build(mid + 1, r, 2 * node + 2, R, C);
seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
}
void modify(int l, int r, int node, int delta, int where, bool which) {
if (l == r) {
if (which) {
seg[node].R_max = seg[node].R_min = delta;
} else {
seg[node].C_max = seg[node].C_min = delta;
}
return;
}
int mid = l + (r - l) / 2;
if (where <= mid) {
modify(l, mid, 2 * node + 1, delta, where, which);
}
if (where >= mid + 1) {
modify(mid + 1, r, 2 * node + 2, delta, where, which);
}
seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
}
Node query(int ql, int qr, int l, int r, int node) {
if (l >= ql && r <= qr) return seg[node];
int mid = (l + r) >> 1;
Node esq;
if (ql <= mid) {
esq = query(ql, qr, l, mid, 2 * node + 1);
}
Node dir;
if (qr >= mid + 1) {
dir = query(ql, qr, mid + 1, r, 2 * node + 2);
}
Node ans;
ans.merge(esq, dir);
return ans;
}
};
SegmentTree *seg;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
::H = H; ::W = W;
::R = R; ::C = C;
::HI = H * W;
seg = new SegmentTree;
}
int swap_seats(int a, int b) {
swap(R[a], R[b]);
swap(C[a], C[b]);
seg -> modify(LO, HI - 1, 0, R[a], a, true);
seg -> modify(LO, HI - 1, 0, C[a], a, false);
seg -> modify(LO, HI - 1, 0, R[b], b, true);
seg -> modify(LO, HI - 1, 0, C[b], b, false);
int res = 0;
int current_idx = 0;
while(current_idx < HI) {
Node ans = seg -> query(0, current_idx, LO, HI - 1, 0);
int score = (ans.R_max - ans.R_min + 1) * (ans.C_max - ans.C_min + 1);
if (current_idx + 1 == score) {
++res;
++current_idx;
} else {
current_idx = score - 1;
}
}
return res;
}