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>
using namespace std;
using ari2 = array<int, 2>;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N, D;
cin >> N >> D;
vector<int> A(N);
for (int &i : A) {
cin >> i;
}
struct Segtree {
vector<int> sgt;
Segtree(int n) {
sgt.resize(n<<2, 0);
}
void upd(int p, int v, int i = 1, int tl = 0, int tr = -1) {
if (tr < 0) tr += sgt.size() >> 2;
if (tl == tr) {
sgt[i] = max(sgt[i], v);
} else {
int tm = tl + tr >> 1;
p > tm ? upd(p, v, i<<1|1, tm+1, tr) : upd(p, v, i<<1, tl, tm);
sgt[i] = max(sgt[i<<1], sgt[i<<1|1]);
}
}
int qry(int ql, int qr, int i = 1, int tl = 0, int tr = -1) {
if (tr < 0) tr += sgt.size() >> 2;
if (tl > qr || tr < ql) return 0;
if (ql <= tl && tr <= qr) return sgt[i];
int tm = tl + tr >> 1;
return max(qry(ql, qr, i<<1, tl, tm), qry(ql, qr, i<<1|1, tm+1, tr));
}
} sgt(N);
vector<int> ord(N);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](const int &a, const int &b) {
return A[a] != A[b] ? A[a] < A[b] : a > b;
});
struct DSU {
vector<int> uf, L;
DSU(int n) {uf.resize(n, -1); L.resize(n, 0); iota(L.begin(), L.end(), 0);}
int find(int f) {return uf[f] < 0 ? f : uf[f] = find(uf[f]);}
void unite(int a, int b) {
if ((a = find(a)) == (b = find(b))) return;
if (uf[a] > uf[b]) swap(a, b);
uf[a] += uf[b], uf[b] = a;
L[a] = min(L[a], L[b]);
}
int getL(int i) {return L[find(i)];}
} uf(N);
set<int> in;
for (int i : ord) {
auto it = in.lower_bound(i);
if (it != in.begin() && *--it + D >= i) {
uf.unite(*it, i);
}
sgt.upd(i, sgt.qry(uf.getL(i), i) + 1);
in.insert(i);
}
cout << sgt.qry(0, N-1) << '\n';
}
Compilation message (stderr)
Main.cpp: In member function 'void main()::Segtree::upd(int, int, int, int, int)':
Main.cpp:25:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
25 | int tm = tl + tr >> 1;
| ~~~^~~~
Main.cpp: In member function 'int main()::Segtree::qry(int, int, int, int, int)':
Main.cpp:34:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
34 | int tm = tl + tr >> 1;
| ~~~^~~~
# | 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... |