Submission #739654

#	Time	Username	Problem	Language	Result	Execution time	Memory
739654		asdfgrace	Global Warming (CEOI18_glo)	C++17	0 / 100	48 ms	5720 KiB

glo

#include <bits/stdc++.h>
using namespace std;

struct S {
  int n, k;
  vector<int> a, b;

  void run() {
    cin >> n >> k;
    a.resize(n); b.resize(n, k);
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
      b[i] += a[i];
    }
    reverse(b.begin(), b.end());
    
    vector<int> lis;
    vector<pair<int, int>> dpa(n); // {location, old val}
    for (int i = 0; i < n; ++i) {
      int pos = upper_bound(lis.begin(), lis.end(), a[i]) - lis.begin();
      if (pos == lis.size()) {
        dpa[i] = {pos, -1};
        lis.push_back(a[i]);
      } else {
        dpa[i] = {pos, lis[pos]};
        lis[pos] = a[i];
      }
    }
    reverse(dpa.begin(), dpa.end());
    
    
    int ans = lis.size();
    vector<int> lds;
    for (int i = 0; i < n; ++i) {
      lis[dpa[i].first] = dpa[i].second;
      if (lis[dpa[i].first] == -1) lis.pop_back();
      // find first element smaller than b[i]
      int pos = upper_bound(lds.begin(), lds.end(), b[i], greater<int>())
        - lds.begin();
      if (pos == lds.size()) {
        lds.push_back(b[i]);
      } else {
        lds[pos] = b[i];
      }
      int bad = lds.end() - lower_bound(lds.begin(), lds.end(),
        lis.back(), greater<int>());
      ans = max(ans, int(lis.size() + lds.size() - bad));
    }
    
    cout << ans << '\n';
  }
};

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  auto sol = make_unique<S>();
  sol->run();
}

Compilation message (stderr)

glo.cpp: In member function 'void S::run()':
glo.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |       if (pos == lis.size()) {
      |           ~~~~^~~~~~~~~~~~~
glo.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |       if (pos == lds.size()) {
      |           ~~~~^~~~~~~~~~~~~

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