Submission #696850

#TimeUsernameProblemLanguageResultExecution timeMemory
696850tamthegodFinancial Report (JOI21_financial)C++17
60 / 100
4124 ms652208 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]; int mark[maxN]; vector<int> close[maxN]; struct Trie { const int base = 19; struct TNode { int id, cnt; int child[2]; }; vector<TNode> tree; void new_node() { TNode tmp; tmp.id = tree.size(); tmp.cnt = 0; for(int i=0; i<2; i++) tmp.child[i] = -1; tree.pb(tmp); } void add(int x) { int id = 0; for(int i=base; i>=0; i--) { int w = (x >> i) & 1; if(tree[id].child[w] == -1) { new_node(); tree[id].child[w] = tree.size() - 1; } id = tree[id].child[w]; tree[id].cnt++; } } void del(int x) { int id = 0; for(int i=base; i>=0; i--) { int w = (x >> i) & 1; if(tree[id].child[w] == -1) { new_node(); tree[id].child[w] = tree.size() - 1; } id = tree[id].child[w]; tree[id].cnt--; } } int get() { int id = 0; int res = 0; for(int i=base; i>=0; i--) { if(id == -1) return res; if(tree[id].child[1] != -1 && tree[tree[id].child[1]].cnt) { res += 1 << i; id = tree[id].child[1]; } else id = tree[id].child[0]; } return res; } } st[4 * maxN]; void build(int id, int l, int r) { st[id].new_node(); 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].add(val); id /= 2; } } void del(int pos, int val) { int id = mark[pos]; while(id) { st[id].del(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) return st[id].get(); 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...