이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define vt vector
#define pb push_back
#define all(x) x.begin(),x.end()
#define FORR1(x) for(int i = 0; i < (x); i++)
#define FORR2(j,x) for(int (j) = 0; (j) < (x); (j)++)
#define f first
#define s second
typedef vt<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
map<int,vi> mp;
map<int,int> dic;
int pp[10005];
int sz[10005];
int cst[10005];
int ans[10005][103];
int find(int x){
return (x==pp[x] ? x : pp[x] = find(pp[x]));
}
void join(int a, int b){
if(find(a)==find(b))return;
int u = find(a), v = find(b);
if(sz[u]>sz[v])swap(u,v);
pp[u] = v;
sz[v]+=sz[u];
}
int arr[200005];
int in2[200005];
int out2[200005];
int in1[200005];
int out1[200005];
void solve(){
int n, x;
cin>>n>>x;
FORR1(n)cin>>arr[i];
set<int,greater<>> st2;
for(int i = n-1; i>=0; i--){
auto it = st2.lower_bound(arr[i]);
if(it == st2.end()){
in2[i] = arr[i];
out2[i] = -1;
st2.insert(arr[i]);
}else{
in2[i] = arr[i];
out2[i] = *it;
st2.erase(it);
st2.insert(arr[i]);
}
}
set<int> st1;
FORR1(n){
auto it = st1.lower_bound(arr[i]);
if(it == st1.end()){
in1[i] = arr[i];
out1[i] = -1;
st1.insert(arr[i]);
}else{
in1[i] = arr[i];
out1[i] = *it;
st1.erase(it);
st1.insert(arr[i]);
}
}
int a = st1.size(), b = st2.size();
vi cal1(a), cal2(b);
FORR1(a)cal1[i] = -1;
int att = 0;
for(auto & e: st2){
cal2[att] = e;
att++;
}
int ans = b;
int at1 = -1, at2 = b-1;
FORR1(n){
int l = 0, r = a;
while(l!=r){
int mid = (l+r)>>1;
if(cal1[mid]==-1||(out1[i]!=-1&&out1[i]<cal1[mid])){
r = mid;
}else if(cal1[mid]==out1[i]){
l = mid;
r = mid;
}else{
l = mid+1;
}
}
cal1[l] = in1[i];
l = 0; r = b;
while(l!=r){
int mid = (l+r)>>1;
if(cal2[mid]>in2[i]){
l = mid+1;
}else if(cal2[mid]<in2[i]){
r = mid;
}else{
l = r = mid;
}
}
cal2[l] = out2[i];
if(cal2[at2]==-1){
at2--;
}
if(at1==-1){
if(cal1[0]-cal2[at2]<x){
at1 = 0;
}
}else if(at2!=-1){
if(cal1[at1]-cal2[at2]<x){
if(at1!=a-1&&cal1[at1+1]!=-1&&cal1[at1+1]-cal2[at2]<x){
at1++;
}
}else{
at2--;
}
}
ans = max(ans, at1+at2+2);
/*if(at1+at2+2==6){
cout<<i<<'\n';
cout<<at1<<' '<<at2<<'\n';
}*/
}
ans = max(ans,(int)st1.size());
cout<<ans<<'\n';
}
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |