#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct SegmentTree{
struct Node{
ll mx = 0;
};
vector<Node> T;
int n, N;
SegmentTree(int n) : n(n){
N = 1;
while(N < n) N*=2;
T.resize(N*2+1);
};
void upd(int i, ll x){
auto upd = [&](auto upd, int node, int low, int high, int i, ll x) -> void{
if(low == high){
T[node].mx = max(T[node].mx, x);
return;
}
int mid = (low+high)/2;
if(i <= mid){
upd(upd, node*2, low, mid, i, x);
}else{
upd(upd, node*2+1, mid+1, high, i, x);
}
T[node].mx = max(T[node*2].mx, T[node*2+1].mx);
};
upd(upd, 1, 1, N, i, x);
}
ll get_max(int l, int r){
auto get_max = [&](auto get_max, int node, int low, int high, int l, int r) -> ll{
if(low > r || l > high) return 0;
if(low >= l && r >= high) return T[node].mx;
int mid = (low+high)/2;
return max(get_max(get_max, node*2, low, mid, l, r), get_max(get_max, node*2+1, mid+1, high, l, r));
};
return get_max(get_max, 1, 1, N, l, r);
}
};
struct normalize{
vector<ll> poi, pot;
void add(ll x){
poi.push_back(x);
}
void start(){
sort(poi.begin(), poi.end());
pot.push_back(poi[0]);
for(int i = 1; i < (int)poi.size(); i++){
if(poi[i] != poi[i-1]){
pot.push_back(poi[i]);
}
}
}
int encode(ll x){
return lower_bound(pot.begin(), pot.end(), x) - pot.begin()+1;
}
};
struct point{
ll x, y;
};
bool cmpxr(point a, point b){
return a.x > b.x || (a.x == b.x && a.y > b.y);
}
void solve(){
int n, m;
cin >> n >> m;
vector<point> a(n+1);
vector<ll> b(m+1);
for(int i = 1; i <= n; i++){
cin >> a[i].x >> a[i].y;
}
for(int i = 1; i <= m; i++){
cin >> b[i];
}
normalize norm;
for(int i = 1; i <= n; i++){
norm.add(a[i].x);
norm.add(a[i].y);
norm.add(b[i]);
}
norm.start();
for(int i = 1; i <= n; i++){
a[i].x = norm.encode(a[i].x);
a[i].y = norm.encode(a[i].y);
}
for(int i = 1; i <= m; i++){
b[i] = norm.encode(b[i]);
}
sort(b.begin()+1, b.end(), greater<ll>());
b.push_back(-INF);
sort(a.begin()+1, a.end(), cmpxr);
vector<ll> dp(n+1, 0);
int N = n*2+m+1;
SegmentTree T(N+1);
ll ans = 0;
for(int i = 1; i <= n; i++){
ll mx = T.get_max(a[i].y, N)+1;
ll j = upper_bound(b.begin()+1, b.end(), a[i].x) - b.begin()-1;
if(j == m+1) j = 0;
mx = min(mx, j);
dp[i] = mx;
T.upd(a[i].y, dp[i]);
ans = max(ans, dp[i]);
}
cout << ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
