Submission #699886

#	Time	Username	Problem	Language	Result	Execution time	Memory
699886		nima_aryan	Global Warming (CEOI18_glo)	C++14	100 / 100	56 ms	6164 KiB

glo

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

const int inf = 1e9;

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int n, x;
   cin >> n >> x;
   vector<int> t(n);
   for (int i = 0; i < n; ++i) {
      cin >> t[i];
   }
   vector<int> prefix_dp(n, inf), prefix_lis(n);
   for (int i = 0; i < n; ++i) {
      int j = (int) distance(prefix_dp.begin(),
                             lower_bound(
                                prefix_dp.begin(), prefix_dp.end(),
                                t[i]
                             )
                            );
      prefix_dp[j] = t[i];
      prefix_lis[i] = j + 1;
   }
   vector<int> suffix_dp(n, inf), suffix_lis(n);
   for (int i = n - 1; i >= 0; --i) {
      suffix_lis[i] = (int) distance(suffix_dp.begin(),
                                     lower_bound(
                                        suffix_dp.begin(), suffix_dp.end(),
                                        -(t[i] - x)
                                     )
                                    );
      int j = (int) distance(suffix_dp.begin(),
                             lower_bound(
                                suffix_dp.begin(), suffix_dp.end(),
                                -t[i]
                             )
                            ) ;
      suffix_dp[j] = -t[i];
   }
   int ans = 0;
   for (int i = 0; i < n; ++i) {
      ans = max(ans, prefix_lis[i] + suffix_lis[i]);
   }
   cout << ans << '\n';
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25