Submission #739659

#	Time	Username	Problem	Language	Result	Execution time	Memory
739659		asdfgrace	Global Warming (CEOI18_glo)	C++17	62 / 100	49 ms	9420 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << '\n')
#define PV2(x) DEBUG(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << "  "); PRINT("}\n");)
typedef int64_t i64;
const int INF = 1000000007; //998244353;

struct S {
  i64 n, k;
  vector<i64> 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());
    PAR(a); PAR(b);
    
    vector<i64> lis;
    vector<pair<i64, i64>> dpa(n); // {location, old val}
    for (int i = 0; i < n; ++i) {
      i64 pos = lower_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];
      }
    }
    PAR(lis);
    reverse(dpa.begin(), dpa.end());
    PAR2(dpa);
    
    
    i64 ans = lis.size();
    vector<i64> 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]
      i64 pos = lower_bound(lds.begin(), lds.end(), -b[i]) - lds.begin();
      PV(pos);
      if (pos == lds.size()) {
        lds.push_back(-b[i]);
      } else {
        lds[pos] = -b[i];
      }
      i64 bad = (lis.size() ? lds.end() - lower_bound(lds.begin(), lds.end(),
        -lis.back()) : 0);
      PV(bad);
      ans = max(ans, i64(lis.size() + lds.size() - bad));
      PAR(lis);
      PAR(lds);
      PV(ans);
    }
    
    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:31:15: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |       if (pos == lis.size()) {
      |           ~~~~^~~~~~~~~~~~~
glo.cpp:52:15: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |       if (pos == lds.size()) {
      |           ~~~~^~~~~~~~~~~~~

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