| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 914130 |
2024-01-21T08:43:43 Z |
Alcabel |
None (JOI14_ho_t5) |
C++17 |
|
466 ms |
34424 KB |
#include <bits/stdc++.h>
using namespace std;
struct DSU {
int n, comps;
vector<int> par, sz;
DSU() {}
DSU(int _n) {
n = _n, comps = n;
par.resize(n);
sz.resize(n);
for (int i = 0; i < n; ++i) {
par[i] = i, sz[i] = 1;
}
}
int getParent(int v) {
if (par[v] != v) {
par[v] = getParent(par[v]);
}
return par[v];
}
void uniteSets(int v, int u) {
// cerr << "v: " << v << ", u: " << u << '\n';
v = getParent(v), u = getParent(u);
if (v == u) { return; }
if (sz[v] < sz[u]) { swap(v, u); }
par[u] = v;
sz[v] += sz[u];
--comps;
}
~DSU() {}
};
struct SegTree {
int n, N;
DSU dsu;
vector<int> lazy, sum;
vector<set<int>> leafs;
SegTree() {}
SegTree(int _n, int dsusz) {
n = _n, N = 1;
while (N < n) {
N <<= 1;
}
dsu = DSU(dsusz);
lazy.resize(2 * N, -1);
sum.resize(2 * N);
leafs.resize(N);
}
void push(int v) {
if (v < N) {
if (lazy[2 * v] != -1 && sum[2 * v] > 0) {
// cerr << "pushL\n";
// cerr << v << '\n';
dsu.uniteSets(lazy[2 * v], lazy[v]);
}
if (lazy[2 * v + 1] != -1 && sum[2 * v + 1] > 0) {
// cerr << "pushR\n";
// cerr << v << '\n';
dsu.uniteSets(lazy[2 * v + 1], lazy[v]);
}
lazy[2 * v] = lazy[v];
lazy[2 * v + 1] = lazy[v];
} else {
if (!leafs[v - N].empty()) {
// cerr << "pushLeaf\n";
dsu.uniteSets(lazy[v], *leafs[v - N].begin());
}
}
lazy[v] = -1;
}
void unite(int v, int tl, int tr, int l, int r, int i) {
if (lazy[v] != -1) {
push(v);
}
if (tl >= r || tr <= l) {
return;
}
if (l <= tl && tr <= r) {
lazy[v] = i;
push(v);
return;
}
int m = tl + (tr - tl) / 2;
unite(2 * v, tl, m, l, r, i);
unite(2 * v + 1, m, tr, l, r, i);
}
void unite(int l, int r, int i) {
unite(1, 0, N, l, r, i);
}
void change(int v, int tl, int tr, int pos, int i, int flag) {
if (lazy[v] != -1) {
push(v);
}
if (tl >= pos + 1 || tr <= pos) {
return;
}
if (tl + 1 == tr) {
if (flag > 0) {
// insert
if (!leafs[v - N].empty()) {
// cerr << "when change\n";
dsu.uniteSets(*leafs[v - N].begin(), i);
}
leafs[v - N].emplace(i);
} else {
// erase
leafs[v - N].erase(i);
}
sum[v] = !leafs[v - N].empty();
return;
}
int m = tl + (tr - tl) / 2;
change(2 * v, tl, m, pos, i, flag);
change(2 * v + 1, m, tr, pos, i, flag);
sum[v] = sum[2 * v] + sum[2 * v + 1];
}
void change(int pos, int i, int flag) {
change(1, 0, N, pos, i, flag);
}
int getSum(int l, int r) {
int vl = N + l, vr = N + r, res = 0;
while (vl < vr) {
if (vl & 1) {
res += sum[vl];
}
if ((vr ^ 1) & 1) {
res += sum[vr];
}
vl = (vl + 1) >> 1;
vr = (vr - 1) >> 1;
}
if (vl == vr) {
res += sum[vl];
}
return res;
}
~SegTree() {}
};
struct Event {
int lx, rx, y, type, i;
Event() {}
Event(int _lx, int _rx, int _y, int _type, int _i) {
lx = _lx, rx = _rx, y = _y, type = _type, i = _i;
}
bool operator<(const Event& other) const {
return make_pair(y, type) < make_pair(other.y, other.type);
}
~Event() {}
};
void solve() {
int w, h, n;
cin >> w >> h >> n;
vector<vector<int>> cuts(n + 4, vector<int>(4));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 4; ++j) {
cin >> cuts[i][j];
}
}
cuts[n] = {0, 0, 0, h};
cuts[n + 1] = {0, h, w, h};
cuts[n + 2] = {w, 0, w, h};
cuts[n + 3] = {0, 0, w, 0};
n += 4;
vector<Event> evs;
vector<int> allX;
auto getX = [&](int x) {
return lower_bound(allX.begin(), allX.end(), x) - allX.begin();
};
auto calc = [&]() -> vector<long long> {
SegTree st(allX.size(), n);
set<pair<int, int>> segs;
vector<long long> res = {0, 0, 0};
for (int l = 0; l < (int)evs.size(); ++l) {
if (evs[l].type == 0) {
segs.clear();
int r = l - 1;
while (r + 1 < (int)evs.size() && evs[r + 1].type == 0 && evs[r + 1].y == evs[l].y) {
++r;
st.unite(getX(evs[r].lx), getX(evs[r].rx) + 1, evs[r].i);
int newL = evs[r].lx, newR = evs[r].rx;
auto it = segs.lower_bound(make_pair(evs[r].lx, 0));
while (it != segs.end() && it->second <= evs[r].rx) {
newL = min(newL, it->second);
newR = max(newR, it->first);
it = segs.erase(it);
}
segs.emplace(newR, newL);
}
while (!segs.empty()) {
auto [rx, lx] = *segs.begin();
segs.erase(segs.begin());
int points = st.getSum(getX(lx), getX(rx));
// cerr << "y: " << evs[r].y << ", lx: " << lx << ", rx: " << rx << ", points: " << points << '\n';
res[0] += points, res[1] += max(0, points - 1);
}
l = r;
} else {
// cerr << "y: " << evs[l].y << ", x: " << evs[l].lx << ", type: " << evs[l].type << '\n';
st.change(getX(evs[l].lx), evs[l].i, -evs[l].type);
}
}
res[2] = st.dsu.comps;
// cerr << "res: " << res[0] << ' ' << res[1] << ' ' << res[2] << '\n';
return res;
};
vector<long long> res = {-1, 0, -1};
for (int iter = 0; iter < 2; ++iter) {
allX.clear();
evs.clear();
for (int i = 0; i < n; ++i) {
if (cuts[i][0] == cuts[i][2]) {
// vertical
evs.emplace_back(cuts[i][0], cuts[i][0], cuts[i][1], -1, i);
evs.emplace_back(cuts[i][0], cuts[i][0], cuts[i][3], 1, i);
allX.emplace_back(cuts[i][0]);
} else {
// horizontal
evs.emplace_back(cuts[i][0], cuts[i][2], cuts[i][1], 0, i);
allX.emplace_back(cuts[i][0]);
allX.emplace_back(cuts[i][2]);
}
}
sort(allX.begin(), allX.end());
allX.resize(unique(allX.begin(), allX.end()) - allX.begin());
sort(evs.begin(), evs.end());
vector<long long> tmp = calc();
assert(res[0] == -1 || res[0] == tmp[0]);
assert(res[2] == -1 || res[2] == tmp[2]);
res[0] = tmp[0], res[2] = tmp[2];
res[1] += tmp[1];
for (int i = 0; i < n; ++i) {
swap(cuts[i][0], cuts[i][1]);
swap(cuts[i][2], cuts[i][3]);
}
}
cout << res[1] - res[0] + res[2] << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
4 ms |
604 KB |
Output is correct |
| 3 |
Correct |
34 ms |
3000 KB |
Output is correct |
| 4 |
Correct |
0 ms |
600 KB |
Output is correct |
| 5 |
Correct |
3 ms |
604 KB |
Output is correct |
| 6 |
Correct |
466 ms |
34424 KB |
Output is correct |
| 7 |
Correct |
15 ms |
2488 KB |
Output is correct |
| 8 |
Correct |
178 ms |
21004 KB |
Output is correct |
| 9 |
Correct |
198 ms |
20480 KB |
Output is correct |
| 10 |
Correct |
214 ms |
20732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
