제출 #1099089

#제출 시각아이디문제언어결과실행 시간메모리
1099089LeDaiKingGlobal Warming (CEOI18_glo)C++14
100 / 100
130 ms7120 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define pb push_back #define ALL(n) n.begin(), n.end() #define mask(n) (1ll << (n)) #define ck(n, k) (((n) >> (k))&1) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); class BIT { private: int num; vector<int> fen; public: BIT(int num) { this->num = num; fen.assign(num + 1, 0); } void updateUp(int id, int val) { id = max(id, 1); for (; id <= num; id += (id & (-id))) fen[id] = max(fen[id], val); } void updateDown(int id, int val) { id = min(id, num); for (; id; id -= (id & (-id))) fen[id] = max(fen[id], val); } int getUp(int id) { int ans = 0; id = max(id, 1); for (; id <= num; id += (id & (-id))) ans = max(ans, fen[id]); return ans; } int getDown(int id) { int ans = 0; id = min(id, num); for (; id; id -= (id & (-id))) ans = max(ans, fen[id]); return ans; } }; void solution() { int n, d; cin >> n >> d; vector<int> a(n + 1); vector<int> g(n + 1, 0), f(n + 1, 0); vector<int> compress; for (int i = 1; i <= n; i++) { cin >> a[i]; compress.pb(a[i]); } sort(ALL(compress)); compress.resize(unique(ALL(compress)) - compress.begin()); BIT hntt((int)compress.size()); for (int i = n; i; i--) { int id = lower_bound(ALL(compress), a[i]) - compress.begin() + 1; g[i] = hntt.getUp(id + 1) + 1; hntt.updateDown(id, g[i]); } if (d < 0) d = -d; BIT ldk((int)compress.size()); int ans = 0; for (int i = 1; i <= n; i++) { int w = lower_bound(ALL(compress), a[i] + d) - compress.begin(); // cout << i << " " << w << " " << ldk.getDown(w) + g[i] << " " << g[i] << " "; ans = max(ans, ldk.getDown(w) + g[i]); int id = lower_bound(ALL(compress), a[i]) - compress.begin() + 1; f[i] = ldk.getDown(id - 1) + 1; ldk.updateUp(id, f[i]); // cout << f[i] << " " << id << endl; } // cout << compress[5] << endl; cout << ans; } int main() { //freopen("test.inp", "r", stdin); //freopen("test.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solution(); }
#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...