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>
#define int long long
using namespace std;
map<int, int> mp1, mp2;
int cnt = 0;
int v[200005];
int aib1[200005], aib2[200005];
void upd1(int poz, int val)
{
for(int i = poz; i <= cnt; i += (i & (-i)))
aib1[i] = max(aib1[i], val);
return;
}
int qry1(int poz)
{
int maxx = 0;
for(int i = poz; i >= 1; i -= (i & (-i)))
maxx = max(maxx, aib1[i]);
return maxx;
}
void upd2(int poz, int val)
{
for(int i = poz; i <= cnt; i += (i & (-i)))
aib2[i] = max(aib2[i], val);
return;
}
int qry2(int poz)
{
int maxx = 0;
for(int i = poz; i >= 1; i -= (i & (-i)))
maxx = max(maxx, aib2[i]);
return maxx;
}
signed main()
{
int n, k;
cin>>n>>k;
for(int i = 1; i <= n; i++)
cin>>v[i], mp1[v[i]] = 1, mp1[v[i] - k] = 1;
for(auto it : mp1)
mp2[it.first] = ++cnt;
for(int i = 1; i <= n; i++)
{
upd1(mp2[v[i] - k], qry1(mp2[v[i] - k] - 1) + 1);
upd2(mp2[v[i]], qry1(mp2[v[i]] - 1) + 1);
upd2(mp2[v[i]], qry2(mp2[v[i]] - 1) + 1);
}
cout<<max(qry1(cnt), qry2(cnt));
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... |