#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct PersistentSegmentTree{
struct Node{
int mx = 0;
int ln = 0, rn = 0;
};
int n, N;
vector<Node> nodes;
vector<int> ver;
PersistentSegmentTree(int n): n(n){
N = n;
nodes.push_back({0, 0, 0});
ver.push_back(0);
};
void upd(int &node, int ori, int i, int x){
auto upd = [&](auto upd, int &node, int ori, int low, int high, int i, int x) -> void{
node = nodes.size();
nodes.push_back(nodes[ori]);
if(low == high){
nodes[node].mx = max(nodes[node].mx, x);
return;
}
int mid = (low+high)/2;
Node goat = nodes[node];
if(i <= mid){
upd(upd, goat.ln, nodes[ori].ln, low, mid, i, x);
}else{
upd(upd, goat.rn, nodes[ori].rn, mid+1, high, i, x);
}
goat.mx = max(nodes[goat.ln].mx, nodes[goat.rn].mx);
nodes[node] = goat;
};
upd(upd, node, ori, 1, N, i, x);
}
int get_max(int node, int l, int r){
if(r > 1e9) r = 1e9;
auto get_max = [&](auto get_max, int node, int low, int high, int l, int r) -> int{
if(low > r || l > high){
return 0;
}
if(low >= l && r >= high){
return nodes[node].mx;
}
int mid = (low+high)/2;
return max(get_max(get_max, nodes[node].ln, low, mid, l, r), get_max(get_max, nodes[node].rn, mid+1, high, l, r));
};
return get_max(get_max, node, 1, N, l, r);
}
};
void solve(){
ll n, x;
ll B = 1e9+1;
cin >> n >> x;
vector<ll> a(n+1);
for(int i = 1; i <= n; i++){
cin >> a[i];
}
PersistentSegmentTree Tl(B), Tr(B);
Tl.ver.resize(n+1, 0);
Tr.ver.resize(n+1, 0);
int j = 0;
for(int i = n; i >= 1; i--){
j++;
ll mx = Tr.get_max(Tr.ver[j-1], a[i]+1, B-1)+1;
Tr.upd(Tr.ver[j], Tr.ver[j-1], a[i], mx);
}
j = n;
ll ans = 0;
for(int i = 1; i <= n; i++){
j--;
ll mx = Tl.get_max(Tl.ver[i-1], 1, a[i]-1)+1;
Tl.upd(Tl.ver[i], Tl.ver[i-1], a[i], mx);
ans = max(ans, Tl.get_max(Tl.ver[i], a[i], a[i])+Tr.get_max(Tr.ver[j], a[i]-x+1, a[i]+x-1));
}
cout << ans;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
Compilation message
glo.cpp: In function 'void solve()':
glo.cpp:78:99: error: no matching function for call to 'max(long long int&, int)'
78 | ans = max(ans, Tl.get_max(Tl.ver[i], a[i], a[i])+Tr.get_max(Tr.ver[j], a[i]-x+1, a[i]+x-1));
| ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from glo.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
glo.cpp:78:99: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
78 | ans = max(ans, Tl.get_max(Tl.ver[i], a[i], a[i])+Tr.get_max(Tr.ver[j], a[i]-x+1, a[i]+x-1));
| ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from glo.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
glo.cpp:78:99: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
78 | ans = max(ans, Tl.get_max(Tl.ver[i], a[i], a[i])+Tr.get_max(Tr.ver[j], a[i]-x+1, a[i]+x-1));
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from glo.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
glo.cpp:78:99: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
78 | ans = max(ans, Tl.get_max(Tl.ver[i], a[i], a[i])+Tr.get_max(Tr.ver[j], a[i]-x+1, a[i]+x-1));
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from glo.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
glo.cpp:78:99: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
78 | ans = max(ans, Tl.get_max(Tl.ver[i], a[i], a[i])+Tr.get_max(Tr.ver[j], a[i]-x+1, a[i]+x-1));
| ^
