제출 #940102

#제출 시각아이디문제언어결과실행 시간메모리
940102viwlesxqGlobal Warming (CEOI18_glo)C++17
55 / 100
1134 ms219676 KiB
#include <bits/stdc++.h> using namespace std; //#define int long long #define all(x) x.begin(), x.end() #define size(x) (int)x.size() template<class S, class T> bool chmin(S &a, const T &b) { return a > b ? (a = b) == b : false; } template<class S, class T> bool chmax(S &a, const T &b) { return a < b ? (a = b) == b : false; } struct PST { int n, sz, cnt; vector<int> L, R, root, t, a; void construct(int n, vector<int> arr) { this -> n = n; a = arr, sz = 0, cnt = 1; L.assign(30 * n, 0), R.assign(30 * n, 0); root.assign(30 * n, 0), t.assign(30 * n, 0); root[1] = build(1, n); } int build(int tl, int tr) { int v = ++sz; if (tl == tr) { t[v] = a[tl]; return v; } int tm = (tl + tr) >> 1; L[v] = build(tl, tm); R[v] = build(tm + 1, tr); t[v] = max(t[L[v]], t[R[v]]); return v; } int upd(int v, int tl, int tr, int i, int x) { int nv = ++sz; L[nv] = L[v]; R[nv] = R[v]; if (tl == tr) { t[nv] = x; return nv; } int tm = (tl + tr) >> 1; if (i <= tm) { L[nv] = upd(L[nv], tl, tm, i, x); } else { R[nv] = upd(R[nv], tm + 1, tr, i, x); } t[nv] = max(t[L[nv]], t[R[nv]]); return nv; } void upd(int id, int i, int x) { root[id] = upd(root[id], 1, n, i, x); } int get(int v, int tl, int tr, int l, int r) { if (tl > r || tr < l) { return 0ll; } if (tl >= l && tr <= r) { return t[v]; } int tm = (tl + tr) >> 1; return max(get(L[v], tl, tm, l, r), get(R[v], tm + 1, tr, l, r)); } int get(int id, int l) { if (l > n) return 0ll; return get(root[id], 1, n, l, n); } void copy(int id) { root[++cnt] = root[id]; } }; struct segtree { int n; vector<int> t; void construct(int n) { this -> n = n; t.assign(4 * n + 4, 0); } void upd(int v, int tl, int tr, int i, int delta) { if (tl == tr) { t[v] = delta; return; } int tm = (tl + tr) / 2; if (tm >= i) upd(2 * v, tl, tm, i, delta); else upd(2 * v + 1, tm + 1, tr, i, delta); t[v] = max(t[2 * v], t[2 * v + 1]); } void upd(int i, int delta) { upd(1, 1, n, i, delta); } int get(int v, int tl, int tr, int l, int r) { if (tl > r || tr < l) return 0ll; if (tl >= l && tr <= r) return t[v]; int tm = (tl + tr) / 2; return max(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r)); } int get(int l, int r) { if (l > r) return 0ll; return get(1, 1, n, l, r); } }; PST pst; segtree t; map<int, int> mp; void compress(vector<int> a, int x) { vector<int> v; for (int i = 0; i < size(a); ++i) { if (!mp.count(a[i])) v.push_back(a[i]), mp[a[i]]; if (!mp.count(a[i] - x + 1)) v.push_back(a[i] - x + 1), mp[a[i] - x + 1]; } sort(all(v)); vector<int> constructor; for (int i = 0; i < size(v); ++i) { mp[v[i]] = i + 1; constructor.push_back(0); } constructor.push_back(0); pst.construct(size(v), constructor); t.construct(size(v)); } signed main() { cin.tie(nullptr)->sync_with_stdio(false); int n, x; cin >> n >> x; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } compress(a, x); for (int i = n - 1, idx = 2; i >= 0; --i, ++idx) { pst.copy(idx - 1); int dp = pst.get(idx, mp[a[i]] + 1) + 1; pst.upd(idx, mp[a[i]], dp); } int res = 0; for (int i = 0, idx = n; i < n; ++i, --idx) { int dp = t.get(1, mp[a[i]] - 1) + 1; t.upd(mp[a[i]], dp); chmax(res, dp + pst.get(idx, mp[a[i] - x + 1])); } cout << res; }
#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...