제출 #959431

#제출 시각아이디문제언어결과실행 시간메모리
959431Alkaser_IDFinancial Report (JOI21_financial)C++17
5 / 100
149 ms18868 KiB
#include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #include <queue> using namespace std; typedef long long ll; // second mod 998244353 const ll N = 3e5 + 5; ll a[N], b[N]; struct order { ll i, v; }; bool cmp(order x, order y) { if (x.v == y.v) return x.i > y.i; return x.v < y.v; } ll seg[10 * N]; inline void update(ll node, ll l, ll r, ll ind, ll vl) { if (l == r) return void(seg[node] = vl); ll mid = (l + r) / 2; if (ind <= mid) update(node * 2, l, mid, ind, vl); else update(node * 2 + 1, mid + 1, r, ind, vl); seg[node] = max(seg[node * 2], seg[node * 2 + 1]); } inline void del(ll node, ll l, ll r, ll ind) { if (l == r) return void(seg[node] = 0); ll mid = (l + r) / 2; if (ind <= mid) del(node * 2, l, mid, ind); else del(node * 2 + 1, mid + 1, r, ind); seg[node] = max(seg[node * 2], seg[node * 2 + 1]); } inline ll get(ll node, ll l, ll r, ll lx, ll rx) { if (l >= lx && r <= rx) return seg[node]; if (l > rx || r < lx) return 0; ll mid = (l + r) / 2; ll r1 = get(node * 2, l, mid, lx, rx); ll r2 = get(node * 2 + 1, mid + 1, r, lx, rx); return max(r1, r2); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, d; cin >> n >> d; vector<order> v; for (ll i = 1; i <= n; ++i) { cin >> a[i]; order nw; nw.v = a[i]; nw.i = i; v.push_back(nw); } sort(v.begin(), v.end(), cmp); ll MX = n + 2; for (ll i = 0; i < n; ++i) { a[v[i].i] = i + 1; } ll res = 0; ++MX; for (ll i = n; i > 0; --i) { if (i + d < n) del(1, 1, MX, a[i + d + 1]); ll x = get(1, 1, MX, a[i] + 1, MX); ++x; res = max(res, x); update(1, 1, MX, a[i], x); } cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...