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>
// author : a1abay
#define pb push_back
#define all(v) v.begin(), v.end()
#define int ll
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a*b / (__gcd(a, b)))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
const int inf = 1e9 + 7;
const int inff = 1e18 + 7;
const int sz = 2e5 + 5;
using namespace std;
int n, x;
vector<int> v;
int a[sz];
struct BIT
{
vector<int> t;
void init(){t.resize(sz, 0);}
int get(int i)
{
int r = 0;
for(; i > 0; i -= i & -i)r += t[i];
return r;
}
void upd(int i, int x)
{
for(; i < sz; i += i & -i)t[i] = x;
}
};
int ind(int x)
{
return upper_bound(all(v), x) - v.begin();
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> x;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
v.pb(a[i]);
v.pb(a[i] + x);
}
sort(all(v));
v.erase(unique(all(v)), v.end());
BIT l, r;
l.init();
r.init();
for(int i = 1; i <= n; i++)r.upd(ind(a[i] + x), 1);
int ans = 1;
for(int i = 1; i <= n; i++)
{
l.upd(ind(a[i]), 1);
r.upd(ind(a[i]), -1);
int lx = l.get(ind(a[i])) ;
int rx = r.get(ind(v.back())) - r.get(ind(a[i]));
ans = max(ans, lx + rx);
}
cout << ans;
}
# | 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... |