4

Codeforces Tinkoff Challenge – Elimination Round

 2 years ago
source link: https://www.shuizilong.com/house/archives/codeforces-tinkoff-challenge-elimination-round/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
July 15, 2022

G. Oleg and chess

先考虑网络流。。。是最朴素的二分图匹配。。。
还是设法要减少边的规模。。。我们类比扫描线来做矩形合并。。
从左到右扫描每一列，我们用函数式线段树，就能维护出代表这一列的线段树的根节点状态。。
那么只要从源点向根节点连过去一条容量为 1 的边即可。。注意需要保证这些线段树共享同一组闭合状态。。。

总感觉有更好的做法。。。

const int N = int(1e4) + 9;
int T[N], H[N]; VI adj[N];
int n, m;
namespace Chairman_Tree {
#define lx c[0][x]
#define rx c[1][x]
#define ly c[0][y]
#define ry c[1][y]
#define lz c[0][z]
#define rz c[1][z]
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx, l, ml
#define rc rx, mr, r
const int NN = 100*N;
int c[2][NN]; int tot;
int pp; int dd;
int new_node() {
return ++tot;
}
int new_node(int y) {
int x = ++tot; lx = ly; rx = ry;
return x;
}
void Build(int& x, int l, int r) {
if (l == r) {
x = l;
} else {
x = new_node();
Build(lc);
Build(rc);
}
}
int Insert(int x, int l, int r, int y, int a, int b) {
if (b < l || r < a) return x;
if (a <= l && r <= b) {
return y;
} else {
x = new_node(x);
lx = Insert(lc, ly, a, b);
rx = Insert(rc, ry, a, b);
return x;
}
}
} using namespace Chairman_Tree;
VII del[N], add[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
RD(n); Rush {
int x1, y1, x2, y2; RD(x1, y1, x2, y2); ++x2;
add[x1].PB({y1, y2});
del[x2].PB({y1, y2});
}
atcoder::mf_graph<int> G(NN);
int s = 0, t = n+1; REP_1(i, n) G.add_edge(i, t, 1);
tot = t;
int x; Build(x, 1, n); int o = x, a = 0; REP_1(i, n) {
int y = x;
for (auto e: del[i]) x = Insert(x, 1, n, o, e.fi, e.se);
for (auto e: add[i]) x = Insert(x, 1, n, 0, e.fi, e.se);
if (x != y) {
if (y && a) G.add_edge(s, y, a);
a = 0;
}
++a;
}
if (x) G.add_edge(s, x, a);
FOR_1(x, t+1, tot) {
if (lx) G.add_edge(x, lx, INF);
if (rx) G.add_edge(x, rx, INF);
}
cout << G.flow(s, t) << endl;
}

Posted by xiaodao
Category: 日常


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK