제출 #790950

#제출 시각아이디문제언어결과실행 시간메모리
790950acatmeowmeowGlobal Warming (CEOI18_glo)C++11
100 / 100
416 ms41424 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5; int n, x, arr[N + 5], tree[2][3*4*N + 5]; void update(int layer, int v, int tl, int tr, int k, int x) { if (tl == tr) tree[layer][v] = max(tree[layer][v], x); else { int tm = (tl + tr)/2; if (k <= tm) update(layer, v*2, tl, tm, k, x); else update(layer, v*2 + 1, tm + 1, tr, k, x); tree[layer][v] = max(tree[layer][v*2], tree[layer][v*2 + 1]); } } int query(int layer, int v, int tl, int tr, int l, int r) { if (l > r) return 0; else if (tl == l && tr == r) return tree[layer][v]; else { int tm = (tl + tr)/2; return max(query(layer, v*2, tl, tm, l, min(tm, r)), query(layer, v*2 + 1, tm + 1, tr, max(l, tm + 1), r)); } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> x; for (int i = 1; i <= n; i++) cin >> arr[i]; vector<int> mp; for (int i = 1; i <= n; i++) mp.push_back(arr[i] - 1), mp.push_back(arr[i]), mp.push_back(arr[i] + x - 1); sort(mp.begin(), mp.end()); mp.erase(unique(mp.begin(), mp.end()), mp.end()); auto index = [&](int pos) { return lower_bound(mp.begin(), mp.end(), pos) - mp.begin() + 1; }; int ans = 0, sz = mp.size(); for (int i = 1; i <= n; i++) { int p = index(arr[i] - 1), cur = index(arr[i]), nex = index(arr[i] + x - 1); int res0 = query(0, 1, 1, sz, 1, p) + 1; int res1 = max(query(1, 1, 1, sz, 1, p) + 1, query(0, 1, 1, sz, 1, nex) + 1); update(0, 1, 1, sz, cur, res0); update(1, 1, 1, sz, cur, res1); ans = max({ans, res0, res1}); } cout << ans << '\n'; 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...