제출 #806746

#제출 시각아이디문제언어결과실행 시간메모리
806746gun_ganFinancial Report (JOI21_financial)C++17
100 / 100
626 ms26156 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MX = 3e5 + 5, inf = 1e9; int N, D; int a[MX], id[MX]; struct segtree { int t[4 * MX]; void update(int v, int l, int r, int pos, int val) { if(l > pos || r < pos) return; if(l == r) { t[v] = val; return; } int mid = (l + r) >> 1; update(v * 2 + 0, l, mid + 0, pos, val); update(v * 2 + 1, mid + 1, r, pos, val); t[v] = max(t[v * 2 + 0], t[v * 2 + 1]); } int query(int v, int l, int r, int ql, int qr) { if(ql > r || qr < l) return 0; if(ql <= l && qr >= r) return t[v]; int mid = (l + r) >> 1; return max(query(v * 2 + 0, l, mid + 0, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr)); } } t; vector<pair<int,int>> comp; int getId(int x) { // find < x auto it = lower_bound(comp.begin(), comp.end(), make_pair(x, -inf)); return it - comp.begin(); } int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> N >> D; for(int i = 1; i <= N; i++) { cin >> a[i]; comp.push_back({a[i], i}); } comp.push_back({0, 0}); sort(comp.begin(), comp.end()); int p = 0; for(auto [x, pos] : comp) { id[pos] = p++; } set<pair<int,int>> st, tt; // last D + 1 elements, other elements before last D + 1 int ans = 0; for(int i = 1; i <= N; i++) { while(!tt.empty()) { if(tt.begin()->first < st.begin()->first) { t.update(1, 0, p, id[tt.begin()->second], 0); tt.erase(tt.begin()); } else { break; } } st.insert({a[i], i}); int k = max(t.query(1, 0, p, 0, getId(a[i]) - 1) + 1, t.query(1, 0, p, 0, getId(a[i] + 1) - 1)); ans = max(ans, k); t.update(1, 0, p, id[i], k); if(i - D >= 1) { st.erase({a[i - D], i - D}); tt.insert({a[i - D], i - D}); } } cout << ans << '\n'; }
#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...