Submission #978805

#TimeUsernameProblemLanguageResultExecution timeMemory
978805duckindogGlobal Warming (CEOI18_glo)C++17
0 / 100
392 ms6652 KiB
#include <bits/stdc++.h> using namespace std; const int N = 200'000 + 10; int n, x; int a[N]; vector<int> rrh; int f[N << 2]; void update(int s, int l, int r, int i, int value) { if (i < l || i > r) return; if (l == r) { f[s] = value; return; } int mid = l + r >> 1; update(s << 1, l, mid, i, value); update(s << 1 | 1, mid + 1, r, i, value); f[s] = max(f[s << 1], f[s << 1 | 1]); } int query(int s, int l, int r, int u, int v) { if (v < l || u > r) return 0; if (u <= l && r <= v) return f[s]; int mid = l + r >> 1; return max(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v)); } int fwd[N], bwd[N]; int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> x; for (int i = 1; i <= n; ++i) cin >> a[i]; rrh = vector<int> (a + 1, a + n + 1); sort(rrh.begin(), rrh.end()); rrh.resize(unique(rrh.begin(), rrh.end()) - rrh.begin()); for (int i = 1; i <= n; ++i) { int r = lower_bound(rrh.begin(), rrh.end(), a[i]) - rrh.begin() + 1; fwd[i] = query(1, 1, rrh.size(), 1, r) + 1; update(1, 1, rrh.size(), r, fwd[i]); } memset(f, 0, sizeof f); for (int i = n; i >= 1; --i) { int l = lower_bound(rrh.begin(), rrh.end(), a[i]) - rrh.begin() + 1; bwd[i] = query(1, 1, rrh.size(), l + 1, rrh.size()) + 1; update(1, 1, rrh.size(), l, bwd[i]); } memset(f, 0, sizeof f); int answer = 0; for (int i = 1; i <= n; ++i) { int it = upper_bound(rrh.begin(), rrh.end(), x - a[i]) - rrh.begin(); answer = max(answer, bwd[i] + query(1, 1, rrh.size(), 1, it)); int r = lower_bound(rrh.begin(), rrh.end(), a[i]) - rrh.begin() + 1; update(1, 1, rrh.size(), r, fwd[i]); } memset(f, 0, sizeof f); for (int i = n; i >= 1; --i) { int it = upper_bound(rrh.begin(), rrh.end(), a[i] - x) - rrh.begin() + 1; answer = max(answer, fwd[i] + query(1, 1, rrh.size(), it, rrh.size())); int l = lower_bound(rrh.begin(), rrh.end(), a[i]) - rrh.begin() + 1; update(1, 1, rrh.size(), l, bwd[i]); } cout << answer << "\n"; }

Compilation message (stderr)

glo.cpp: In function 'void update(int, int, int, int, int)':
glo.cpp:18:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |   int mid = l + r >> 1;
      |             ~~^~~
glo.cpp: In function 'int query(int, int, int, int, int)':
glo.cpp:25:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |   int mid = l + r >> 1;
      |             ~~^~~
#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...