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 <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int maxn = 3e5+10;
int n, D;
#define lc (v<<1)
#define rc (lc|1)
struct node
{
int l, m, p, s;
node()
{
l = m = p = s = 0;
}
node(int _l, int _m, int _p, int _s)
{
l = _l;
m = _m;
p = _p;
s = _s;
}
inline void upd(const node a, const node b)
{
l = a.l+b.l;
p = a.p;
if(a.p == a.l)
p += b.p;
s = b.s;
if(b.s == b.l)
s += a.s;
m = max(a.s+b.p, max(a.m, b.m));
}
} seg[maxn*4], res;
void build(int l, int r, int v)
{
if(r-l == 1)
return (void)(seg[v] = node(1, 0, 0, 0));
int m = (l+r) / 2;
build(l, m, lc);
build(m, r, rc);
seg[v].upd(seg[lc], seg[rc]);
}
void ass(int l, int r, int p, int v)
{
if(r-l == 1)
return (void)(seg[v] = node(1, 1, 1, 1));
int m = (l+r) / 2;
if(p < m)
ass(l, m, p, lc);
else
ass(m, r, p, rc);
seg[v].upd(seg[lc], seg[rc]);
}
inline void ass(int p)
{
return ass(0, n, p, 1);
}
void _get(int l, int r, int s, int e, int v)
{
if(e <= l or r <= s) return;
if(s <= l and r <= e) return res.upd(res, seg[v]);
int m = (l+r) / 2;
_get(l, m, s, e, lc);
_get(m, r, s, e, rc);
}
inline node get(int s, int e)
{
res = node();
_get(0, n, s, e, 1);
return res;
}
int arr[maxn];
int perm[maxn];
int strt[maxn];
struct mxsgt
{
vector<int> vals;
int n;
mxsgt(int _n)
{
n = _n;
vals = vector<int>(n*4, 0);
}
void ass(int l, int r, int p, int x, int v)
{
if(r-l == 1)
return (void)(vals[v] = x);
int m = (l+r)/2;
if(p < m)
ass(l, m, p, x, lc);
else
ass(m, r, p, x, rc);
vals[v] = max(vals[lc], vals[rc]);
}
int get(int l, int r, int s, int e, int v)
{
if(e <= l or r <= s) return 0;
if(s <= l and r <= e) return vals[v];
int m = (l+r) / 2;
return max(get(l, m, s, e, lc), get(m, r, s, e, rc));
}
inline void ass(int p, int x)
{
ass(0, n, p, x, 1);
}
inline int get(int s, int e)
{
return get(0, n, s, e, 1);
}
};
inline int bisect(int l, int r)
{
if(get(l, r).m < D) return l;
int i = r;
while(r-l > 1)
{
int m = (l+r) / 2;
if(get(m, i).m >= D)
l = m;
else
r = m;
}
return l;
}
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> D;
for(int i = 0; i < n; i++)
cin >> arr[i];
iota(perm, perm+n, 0);
sort(perm, perm+n, [&](int i, int j){return arr[i] < arr[j] or (arr[i] == arr[j] and i > j);});
//for(int i = 0; i < n; i++) cerr << perm[i] << " "; cerr << endl;
for(int idx = n-1; idx >= 0; idx--)
{
int i = perm[idx];
ass(i);
strt[i] = bisect(0, i);
}
mxsgt dp(n);
int ans = 0;
for(int idx = 0; idx < n; idx++)
{
int i = perm[idx];
int x = 1+dp.get(strt[i], i);
dp.ass(i, x);
ans = max(ans, x);
}
cout << ans << endl;
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... |