洛谷 2782. 友好城市
原题链接
中等
作者:
czawa
,
2021-10-04 19:13:05
,
所有人可见
,
阅读 200
#include <bits/stdc++.h>
using namespace std;
struct node
{
int x, y;
bool operator < (const node & cmp2) const
{
return x < cmp2.x;
}
};
int dp[1000010];
vector <node> a;
bool _Compare(const node & cmp1, const node & cmp2) noexcept
{
return cmp1.x < cmp2.x;
}
node make_node (int x, int y)
{
node xx;
xx.x = x;
xx.y = y;
return xx;
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++)
{
int x, y;
scanf ("%d%d", &x, &y);
a.push_back(make_node(x, y));
}
int len = 0;
sort (a.begin(), a.end(), _Compare);
for (int i = 0; i < a.size(); i ++)
{
int l = 0, r = len;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (dp[mid] < a[i].y)
l = mid;
else
r = mid - 1;
}
len = max(len, r + 1);
dp[r + 1] = a[i].y;
}
printf ("%d\n", len);
return 0;
}