Skip to content

Instantly share code, notes, and snippets.

@winger

winger/G_solution.cpp Secret

Created Apr 24, 2017
Embed
What would you like to do?
void solve(istream& in, ostream& out) {
int n = next<int>(in);
Graph g;
Graph::Node s = g.addNode(), t = g.addNode();
auto cap = g.arcMap<int>();
vector<vector<Graph::Node>> levelsIn, levelsOut;
levelsIn.push_back(g.addNodes(n));
levelsOut.push_back(g.addNodes(n));
forn (int, i, n) {
g.addEdge(s, levelsIn[0][i]).withUV(cap, 1);
g.addEdge(levelsOut[0][i], t).withUV(cap, 1);
}
for (int l = 1; (1 << l) <= n; ++l) {
levelsIn.push_back(g.addNodes(n - (1 << l) + 1));
levelsOut.push_back(g.addNodes(n - (1 << l) + 1));
forn (int, i, n - (1 << l) + 1) {
g.addEdge(levelsIn[l - 1][i], levelsIn[l][i]).withUV(cap, n);
g.addEdge(levelsIn[l - 1][i + (1 << (l - 1))], levelsIn[l][i]).withUV(cap, n);
g.addEdge(levelsOut[l][i], levelsOut[l - 1][i]).withUV(cap, n);
g.addEdge(levelsOut[l][i], levelsOut[l - 1][i + (1 << (l - 1))]).withUV(cap, n);
}
}
int qs = next<int>(in);
using evt = tuple<int, int, pair<int, int>>;
vector<evt> evs;
forn (int, q, qs) {
int x1 = next<int>(in) - 1;
int y1 = next<int>(in) - 1;
int x2 = next<int>(in) - 1;
int y2 = next<int>(in) - 1;
evs.push_back(evt{x1, +1, {y1, y2 + 1}});
evs.push_back(evt{x2 + 1, -1, {y1, y2 + 1}});
}
evs.push_back(evt{0, -1, {0, n}});
evs.push_back(evt{n, +1, {0, n}});
sort(all(evs));
auto insertRect = [&](int x0, int x1, int y0, int y1) {
if (x0 == x1 || y0 == y1) {
return;
}
int dx = 0, dy = 0;
while (x0 + (1 << (dx + 1)) <= x1) {
++dx;
}
while (y0 + (1 << (dy + 1)) <= y1) {
++dy;
}
auto u = g.addNode();
g.addEdge(levelsIn[dx][x0], u).withUV(cap, n);
g.addEdge(levelsIn[dx][x1 - (1 << dx)], u).withUV(cap, n);
g.addEdge(u, levelsOut[dy][y0]).withUV(cap, n);
g.addEdge(u, levelsOut[dy][y1 - (1 << dy)]).withUV(cap, n);
dbg(x0 + 1, y0 + 1, x1, y1, u.id);
};
map<int, pair<int, int>> ranges;
for (auto& e : evs) {
int x = get<0>(e);
auto& range = get<2>(e);
if (get<1>(e) == -1) {
ranges[range.first] = {range.second, x};
} else {
auto it = ranges.upper_bound(range.first);
--it;
pair<int, int> outer;
outer.first = it->first;
while (it != ranges.end() && it->first < range.second) {
insertRect(it->second.second, x, it->first, it->second.first);
outer.second = it->second.first;
auto jt = it;
it++;
ranges.erase(jt);
}
if (outer.first < range.first) {
ranges[outer.first] = {range.first, x};
}
if (range.second < outer.second) {
ranges[range.second] = {outer.second, x};
}
}
}
PushRelabel<int> f(g, cap);
out << f.run(s, t) << "\n";
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment