![]()
1 #include <bits/stdc++.h>
2 #define dbg(x) cout << #x << "=" << x << endl
3 #define eps 1e-8
4 #define pi acos(-1.0)
5
6 using namespace std;
7 typedef long long LL;
8
9 template<class T>inline void read(T &res)
10 {
11 char c;T flag=1;
12 while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
13 while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
14 }
15
16 namespace _buff {
17 const size_t BUFF = 1 << 19;
18 char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
19 char getc() {
20 if (ib == ie) {
21 ib = ibuf;
22 ie = ibuf + fread(ibuf, 1, BUFF, stdin);
23 }
24 return ib == ie ? -1 : *ib++;
25 }
26 }
27
28 int qread() {
29 using namespace _buff;
30 int ret = 0;
31 bool pos = true;
32 char c = getc();
33 for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
34 assert(~c);
35 }
36 if (c == '-') {
37 pos = false;
38 c = getc();
39 }
40 for (; c >= '0' && c <= '9'; c = getc()) {
41 ret = (ret << 3) + (ret << 1) + (c ^ 48);
42 }
43 return pos ? ret : -ret;
44 }
45
46 const int maxn = 1e5 + 7;
47
48 int n;
49
50 struct node {
51 int x,y,id;
52 }a[maxn];
53
54 bool cmp(node a, node b) {
55 return a.x > b.x;
56 }
57
58 int tot[maxn];///在哪个堆
59 int f[maxn];
60
61 int main()
62 {
63 scanf("%d",&n);
64 for(int i = 1; i <= n; ++i) {
65 scanf("%d %d",&a[i].x, &a[i].y);
66 a[i].id = i;///类似并查集那样先把自己设成祖先
67 }
68 sort(a+1, a+n+1, cmp);
69 int len = 1;
70 f[len] = a[1].y;tot[a[1].id]++;
71 for(int i = 2; i <= n; ++i) {
72 if(a[i].y >= f[len]) {///保证下降
73 f[++len] = a[i].y;
74 tot[a[i].id] = len;
75 }
76 else {
77 int p = lower_bound(f+1, f+len+1, a[i].y) - f;
78 f[p] = a[i].y;
79 tot[a[i].id] = p;
80 }
81 }
82 printf("%d
",len);
83 for(int i = 1; i <= n; ++i) {
84 if(i == 1) printf("%d", tot[i]);
85 else {
86 printf(" %d",tot[i]);
87 }
88 }
89 puts("");
90 return 0;
91 }
