제출 #696847

#제출 시각아이디문제언어결과실행 시간메모리
696847tamthegodFinancial Report (JOI21_financial)C++17
60 / 100
4104 ms376088 KiB
// Make the best become better // No room liftor laziness #include<bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define pb push_back #define lifti liftirst #define se second using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 3e5 + 5; const int mod = 1e9 + 7; const ll oo = 1e9; int n, d; int a[maxN]; int t[maxN]; int f[maxN]; int lab[maxN]; vector<int> vc[maxN]; int dp[maxN]; multiset<int> st[4 * maxN]; int mark[maxN]; vector<int> close[maxN]; void build(int id, int l, int r) { if(l == r) { mark[l] = id; return; } int mid = (l + r) / 2; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); } void add(int pos, int val) { int id = mark[pos]; while(id) { st[id].insert(val); id /= 2; } } void del(int pos, int val) { int id = mark[pos]; while(id) { st[id].erase(st[id].find(val)); id /= 2; } } int get(int id, int l, int r, int u, int v) { if(l > v || r < u) return 0; if(l >= u && r <= v) { auto it = st[id].end(); if(it == st[id].begin()) return 0; return *--it; } int mid = (l + r) / 2; return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v)); } int Findset(int u) { return lab[u] < 0 ? u : lab[u] = Findset(lab[u]); } void Unite(int u, int v) { int r = Findset(u), s = Findset(v); if(r == s) return; if(lab[r] > lab[s]) swap(r, s); dp[r] = max(dp[r], dp[s]); lab[r] += lab[s]; lab[s] = r; } void ReadInput() { vector<int> vc; cin >> n >> d; for(int i=1; i<=n; i++) { cin >> a[i]; vc.pb(a[i]); } sort(vc.begin(), vc.end()); vc.erase(unique(vc.begin(), vc.end()), vc.end()); for(int i=1; i<=n; i++) a[i] = upper_bound(vc.begin(), vc.end(), a[i]) - vc.begin(); } void Solve() { memset(lab, -1, sizeof lab); for(int i=1; i<=n; i++) vc[a[i]].pb(i); for(int i=1; i<=n; i++) dp[i] = i; set<int> S; for(int val=1; val<=n; val++) { for(int v : vc[val]) { auto it = S.lower_bound(v - d); if(it != S.end() && abs(v - *it) <= d) Unite(*it, v); it = S.upper_bound(v + d); if(it != S.begin()) { it--; if(abs(v - *it) <= d) Unite(*it, v); } S.insert(v); } for(int v : vc[val]) { t[v] = min(n, dp[Findset(v)] + d); } } build(1, 1, n); for(int i=1; i<=n; i++) close[t[i]].pb(i); for(int i=1; i<=n; i++) { f[i] = get(1, 1, n, 1, a[i] - 1) + 1; add(a[i], f[i]); for(int v : close[i]) del(a[v], f[v]); } cout << *max_element(f + 1, f + n + 1); } int32_t main() { //freopen("sol.inp", "r", stdin); // freopen("sol.out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(nullptr); ReadInput(); Solve(); } // 2 3 8 5 8 7 8 10 10 10
#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...