题解
线段覆盖类型的题目。先对端点排序，然后从左到右扫描，对线段依次分配。用一个堆来管理空出来的牛棚。
当端点重合时先分配再释放。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
struct Q{
int id, x;
};
struct cmp{
bool operator ()(const Q& q1, const Q& q2){
return q1.x < q2.x;
}
};
int n, l[50005], r[50005], ans[50005] = {0};
Q q[100005];
priority_queue<int, vector<int>, greater<int> > pq;
void init(){
n = read();
for(int i = 0; i < n; ++i)
l[i] = read(), r[i] = read(),
q[i << 1].id = q[i << 1 | 1].id = i,
q[i << 1].x = l[i], q[i << 1 | 1].x = r[i];
sort(q, q + n + n, cmp());
}
void solve(){
int ans_ = 0;
for(int i = 0; i < n + n; ){
int j;
for(j = i; j < n + n && q[j].x == q[i].x; ++j)
if(!ans[q[j].id]) {
if(pq.empty()) ans_++, ans[q[j].id] = -ans_;
else ans[q[j].id] = -pq.top(), pq.pop();
}
for(j = i; j < n + n && q[j].x == q[i].x; ++j){
if(ans[q[j].id] < 0) ans[q[j].id] = -ans[q[j].id];
else pq.push(ans[q[j].id]);
}
i = j;
}
printf("%d\n", ans_);
for(int i = 0; i < n; ++i)
printf("%d\n", ans[i]);
}
int main(){
init();
solve();
return 0;
}