This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
Compilation message (stderr)
joi2019_ho_t2.cpp:18:14: error: could not convert '-(int)mod' from 'int' to 'std::vector<std::pair<int, int> >'
18 | node UND = {-mod, -mod};
| ^~~~
| |
| int
joi2019_ho_t2.cpp:20:10: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
20 | auto cmp(auto A, auto B){
| ^~~~
joi2019_ho_t2.cpp:20:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
20 | auto cmp(auto A, auto B){
| ^~~~
joi2019_ho_t2.cpp: In member function 'node Segtree::merge(node, node)':
joi2019_ho_t2.cpp:37:14: error: 'struct node' has no member named 'vec'
37 | auto &v = A.vec, &v1 = B.vec;
| ^~~
joi2019_ho_t2.cpp:38:28: error: 'v1' was not declared in this scope; did you mean '__pstl::execution::v1'?
38 | while(i < v.size() || j < v1.size()){
| ^~
| __pstl::execution::v1
In file included from /usr/include/c++/10/pstl/glue_algorithm_defs.h:15,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from joi2019_ho_t2.cpp:1:
/usr/include/c++/10/pstl/execution_defs.h:19:18: note: '__pstl::execution::v1' declared here
19 | inline namespace v1
| ^~
joi2019_ho_t2.cpp:40:8: error: 'struct node' has no member named 'vec'
40 | res.vec.push_back(v1[j]);
| ^~~
joi2019_ho_t2.cpp:43:8: error: 'struct node' has no member named 'vec'
43 | res.vec.push_back(v[i]);
| ^~~
joi2019_ho_t2.cpp:46:8: error: 'struct node' has no member named 'vec'
46 | res.vec.push_back(v[i]);
| ^~~
joi2019_ho_t2.cpp:49:8: error: 'struct node' has no member named 'vec'
49 | res.vec.push_back(v1[j]);
| ^~~
joi2019_ho_t2.cpp:53:18: error: 'struct node' has no member named 'suf'
53 | auto &suf = res.suf;
| ^~~
joi2019_ho_t2.cpp:54:18: error: 'struct node' has no member named 'vec'
54 | for(int i = res.vec.size() - 1; i >= 0; i--){
| ^~~
joi2019_ho_t2.cpp:55:39: error: 'struct node' has no member named 'vec'
55 | if(suf.empty() or suf.back() >= res.vec[i].ss) suf.push_back(res.vec[i].ss);
| ^~~
joi2019_ho_t2.cpp:55:68: error: 'struct node' has no member named 'vec'
55 | if(suf.empty() or suf.back() >= res.vec[i].ss) suf.push_back(res.vec[i].ss);
| ^~~
joi2019_ho_t2.cpp: In member function 'void Segtree::update(int, std::pair<int, int>, int, int, int)':
joi2019_ho_t2.cpp:64:11: error: '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'struct node'} has no member named 'ans'
64 | if(t[v].ans > x.ff) return;
| ^~~
joi2019_ho_t2.cpp:65:11: error: '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'struct node'} has no member named 'ans'
65 | if(t[v].ans == x.ff && t[v].mx < x.ss) return;
| ^~~
joi2019_ho_t2.cpp:65:31: error: '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'struct node'} has no member named 'mx'
65 | if(t[v].ans == x.ff && t[v].mx < x.ss) return;
| ^~
joi2019_ho_t2.cpp:66:21: error: no match for 'operator=' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'node'} and '<brace-enclosed initializer list>')
66 | t[v] = {x.ff, x.ss};
| ^
joi2019_ho_t2.cpp:13:8: note: candidate: 'node& node::operator=(const node&)'
13 | struct node{
| ^~~~
joi2019_ho_t2.cpp:13:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const node&'
joi2019_ho_t2.cpp:13:8: note: candidate: 'node& node::operator=(node&&)'
joi2019_ho_t2.cpp:13:8: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'node&&'
joi2019_ho_t2.cpp: In function 'int main()':
joi2019_ho_t2.cpp:125:20: error: 'struct node' has no member named 'mx'
125 | int to = max(got.mx + 1, (int)(lower_bound(all(frame), A) - frame.begin()));
| ^~
joi2019_ho_t2.cpp:126:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | if(to < frame.size())
| ~~~^~~~~~~~~~~~~~
joi2019_ho_t2.cpp:127:22: error: 'struct node' has no member named 'ans'
127 | seg.update(A, {got.ans+1, to}, 1, 0, SIZ);
| ^~~
joi2019_ho_t2.cpp:127:43: error: cannot convert '<brace-enclosed initializer list>' to 'std::pair<int, int>'
127 | seg.update(A, {got.ans+1, to}, 1, 0, SIZ);
| ^
joi2019_ho_t2.cpp:62:39: note: initializing argument 2 of 'void Segtree::update(int, std::pair<int, int>, int, int, int)'
62 | void update(int pos, pair<int, int> x, int v, int vl, int vr){
| ~~~~~~~~~~~~~~~^
joi2019_ho_t2.cpp:131:15: error: 'struct node' has no member named 'ans'
131 | cout << got.ans;
| ^~~