Submission #698030

#TimeUsernameProblemLanguageResultExecution timeMemory
698030winthemcut3Global Warming (CEOI18_glo)C++14
10 / 100
132 ms16096 KiB
#include <bits/stdc++.h> #define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define ll long long #define int ll #define PB push_back #define ALL(v) (v).begin(), (v).end() #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++) #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--) #define fi first #define se second #define BIT(x, i) (((x) >> (i)) & 1) using namespace std; /** END OF TEMPLATE **/ const int mxN = 2e5 + 5; int n, d; int f1[mxN], f2[mxN], a[mxN], b[mxN]; struct fenwick { vector<int> bit; fenwick(int t) { bit.resize(t + 1, 0); } void update(int id, int val) { for(; id <= 2*n; id += id&-id) bit[id] = max(bit[id], val); } ll get(int id) { int temp = 0; for(; id > 0; id -= id&-id) temp = max(temp, bit[id]); return temp; } }; signed main() { FastIO; //freopen(".inp", "r", stdin); //freopen(".out", "w", stdout); cin >> n >> d; vector<int> t; FOR(i, 1, n) { cin >> a[i]; t.PB(a[i]); t.PB(a[i] + d); } sort(ALL(t)); FOR(i, 1, n) a[i] = lower_bound(ALL(t), a[i]) - t.begin() + 1, b[i] = lower_bound(ALL(t), a[i] + d) - t.begin() + 1; fenwick T1(2*n+1); FOR(i, 1, n) { f1[i] = T1.get(a[i]-1) + 1; T1.update(a[i], f1[i]); } fenwick T(2*n+1); FOR(i, 1, n) { f2[i] = T.get(b[i] - 1) + 1; T.update(a[i], f1[i]); T.update(b[i], f2[i]); } int res = 0; FOR(i, 1, n) res = max(res, max(f1[i], f2[i])); cout << res; 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...
#Verdict Execution timeMemoryGrader output
Fetching results...