| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 919525 | iskhakkutbilim | Exhibition (JOI19_ho_t2) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 1e9 + 7;
const int N = 1e5;
struct node{
vector<pair<int, int> > v;
//int ans, idx;
vector<int> suf_mn;
};
node UND = {-mod, -mod};
auto cmp(auto A, auto B){
if(A.ff != B.ff) return A.ff < B.ff;
return A.ss < B.ss;
}
struct Segtree{
int n;
vector<node> t;
Segtree(int sz){
n = sz;
t.resize(n * 4);
};
node merge(node A, node B){
node res = {{}, {}};
int i = 0, j = 0;
auto &v = A.vec, &v1 = B.vec;
while(i < v.size() || j < v1.size()){
if(i == v.size()){
res.vec.push_back(v1[j]);
j++;
}else if(j == v.size()){
res.vec.push_back(v[i]);
i++;
}else if(cmp(v[i], v1[j])){
res.vec.push_back(v[i]);
i++;
}else{
res.vec.push_back(v1[j]);
j++;
}
}
auto &suf = res.suf;
for(int i = res.vec.size() - 1; i >= 0; i--){
if(suf.empty() or suf.back() >= res.vec[i].ss) suf.push_back(res.vec[i].ss);
else suf.push_back(suf.back());
}
reverse(all(suf));
return res;
}
void update(int pos, pair<int, int> x, int v, int vl, int vr){
if(vl == vr){
if(t[v].ans > x.ff) return;
if(t[v].ans == x.ff && t[v].mx < x.ss) return;
t[v] = {x.ff, x.ss};
return;
}
int mid = (vl + vr)>>1;
if(mid >= pos) update(pos, x, v<<1, vl, mid);
else update(pos, x, v<<1|1, mid+1, vr);
t[v] = merge(t[v<<1], t[v<<1|1]);
}
node get(int l, int r, int v, int vl, int vr){
if(l > vr or vl > r) return UND;
if(l <= vl and r >= vr) return t[v];
int mid = (vl + vr)>>1;
return merge(get(l, r, v<<1, vl, mid), get(l, r, v<<1|1, mid+1, vr));
}
};
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
vector< array<int, 2> > a(n);
for(int i = 0;i < n; i++){
cin >> a[i][0] >> a[i][1];
}
sort(all(a), [&](auto A, auto B){
return A[1] < B[1];
});
vector<int> frame(m);
for(auto &e : frame) cin >> e;
sort(all(frame));
vector<int> x = frame;
for(auto [A, B] : a){
x.push_back(A);
}
sort(all(x));
x.erase(unique(all(x)), x.end());
auto get=[&](int el){
return upper_bound(all(x), el) - x.begin();
};
for(auto &e : frame) e = get(e);
for(auto &[A, B] : a) A = get(A);
int SIZ = x.size();
Segtree seg(SIZ+1);
seg.update(0, {0, 0}, 1, 0, SIZ);
x = frame;
frame.clear();
frame.push_back(0);
for(int e : x) frame.push_back(e);
for(auto [A, NA] : a){
node got = seg.get(0, A, 1, 0, SIZ);
int to = max(got.mx + 1, (int)(lower_bound(all(frame), A) - frame.begin()));
if(to < frame.size())
seg.update(A, {got.ans+1, to}, 1, 0, SIZ);
}
node got = seg.get(0, SIZ, 1, 0, SIZ);
cout << got.ans;
return 0;
}