Submission #1084148

#TimeUsernameProblemLanguageResultExecution timeMemory
1084148yoav_sFinancial Report (JOI21_financial)C++17
5 / 100
154 ms58704 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> p; typedef pair<ll, p> tri; typedef vector<ll> v; typedef vector<v> vv; typedef vector<p> vp; typedef vector<tri> vtri; typedef vector<vtri> vvtri; typedef vector<vvtri> vvvtri; typedef vector<vv> vvv; typedef vector<bool> vb; typedef vector<vb> vvb; typedef vector<vvb> vvvb; typedef vector<p> vp; typedef vector<vp> vvp; typedef vector<vvp> vvvp; typedef vector<vvvp> vvvvp; #define double long double typedef vector<double> vd; typedef vector<vd> vvd; typedef vector<vvd> vvvd; const ll mod = 1e9 + 7; const ll INF = 1e18; #define f first #define s second #define pb push_back #define eb emplace_back #define loop(a) for (ll i = 0; i < a; i++) #define setmin(a, b) a = min(a, b) #define setmax(a, b) a = max(a, b) #define all(v) v.begin(), v.end() void update(v &st, ll i, ll val) { ll n = st.size() / 2; i += n; st[i] = val; i /= 2; while (i > 0) { st[i] = min(st[2 * i], st[2 * i + 1]); i /= 2; } } ll query(v &st, ll l, ll r) { ll n= st.size() / 2; l += n; r += n; ll res = INF; while (l <= r) { if (l % 2 == 1) { res = min(res, st[l]); l++; } if (r % 2 == 0) { res = min(res, st[r]); r--; } l /= 2; r /= 2; } return res; } ll lastSmaller(v &st, ll x) { ll i = 1; ll n = st.size() / 2; if (st[1] >= x) return -1; while (i < n) { if (st[2 * i + 1] < x) i = 2 * i + 1; else i *= 2; } return i - n; } int main() { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); ll N, D; cin >> N >> D; v A(N); for (ll i =0; i < N; i++) cin >> A[i]; ll n = pow(2, ceil(log2(N + 1))); v st(2 * n, INF); update(st, 0, -INF); vector<multiset<ll>> endings(N + 1); endings[0].insert(-INF); for (ll i = 1; i <= N; i++) endings[i].insert(INF); v res(N, -1); ll best = 0; for (ll i = 0; i < N; i++) { ll add = lastSmaller(st, A[i]); if (add != -1) { endings[add + 1].insert(A[i]); best = max(best, add + 1); update(st, add + 1, *endings[add + 1].begin()); res[i] = add + 1; } if (i >= D && res[i - D] != -1) { endings[res[i - D]].erase(endings[res[i - D]].find(A[i - D])); update(st, res[i - D], *endings[res[i - D]].begin()); } } cout << best << "\n"; return 0; }
#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...