Submission #1105823

#TimeUsernameProblemLanguageResultExecution timeMemory
1105823QuocSenseiGlobal Warming (CEOI18_glo)C++14
0 / 100
176 ms10952 KiB
#include <bits/stdc++.h> #define ll long long #define el cout << '\n' using namespace std; const int maxn = 4e5; int n, bitUp[maxn + 10], bitDown[maxn + 10], lis[maxn + 10], ans = 0; vector<ll> v; ll x, a[maxn + 10]; void updateUp(int x, int v) { for (;x <= maxn; x += x&-x) bitUp[x] = max(bitUp[x], v); } int getUp(int x) { int ans = 0; for (;x ; x&=x-1) ans = max(ans, bitUp[x]); return ans; } void updateDown(int x, int v) { for (;x; x&=x-1) bitDown[x] = max(bitDown[x], v); } int getDown(int x) { int ans = 0; for (;x <= maxn; x += x&-x) ans = max(ans, bitDown[x]); return ans; } ll f(ll x) { return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen("GLO.INP", "r")) { freopen("GLO.INP", "r", stdin); freopen("GLO.OUT", "w", stdout); } cin >> n >> x; for (int i = 1; i <= n; i++) { cin >> a[i]; v.push_back(a[i]); v.push_back(a[i] + x); } sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin()); for (int i = n; i >= 1; i--) { int p = getDown(f(a[i]) + 1) + 1; lis[i] = p; updateDown(f(a[i]), p); } for (int i = 1; i <= n; i++) { int p = getUp(f(a[i] + x) - 1) + 1; int u = getUp(f(a[i])) + 1; ans = max(ans, p + lis[i] - 1); updateUp(f(a[i]), u); } cout << ans; }

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen("GLO.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen("GLO.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...