Submission #1213296

#TimeUsernameProblemLanguageResultExecution timeMemory
1213296rhm_ganGlobal Warming (CEOI18_glo)C++20
25 / 100
2095 ms12104 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define dbg(...) 42 #endif vector<int> a, st, lz; void build(int id, int tl, int tr) { if (tl == tr) { st[id] = a[tl]; return; } int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1; build(x, tl, tm); build(y, tm + 1, tr); st[id] = st[x] + st[y]; } void update(int id, int tl, int tr, int l, int r, int v) { if (r < tl || tr < l) return; if (l <= tl && tr <= r) { st[id] += v; lz[id] += v; return; } int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1; update(x, tl, tm, l, r, v); update(y, tm + 1, tr, l, r, v); st[id] = st[x] + st[y] + lz[id]; } int query(int id, int tl, int tr, int i) { if (tl == tr) return st[id]; int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1; if (i <= tm) { return query(x, tl, tm, i) + lz[id]; } else { return query(y, tm + 1, tr, i) + lz[id]; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, x; cin >> n >> x; a.resize(n); st.resize(4 * n); lz.resize(4 * n); for (int i = 0; i < n; i++) { cin >> a[i]; } build(0, 0, n - 1); auto lis = [&]() { set<int> s; for (int i = 0; i < n; i++) { int x = query(0, 0, n - 1, i); auto it = s.lower_bound(x); if (it != s.end()) { s.erase(it); } s.insert(x); } return (int)s.size(); }; if (x == 0) { cout << lis() << '\n'; return 0; } int res = 0; for (int l = 0; l < n; l++) { for (int r = l; r < n; r++) { update(0, 0, n - 1, l, r, -x); res = max(res, lis()); update(0, 0, n - 1, l, r, x); } } cout << res << '\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...