Submission #739685

#	Time	Username	Problem	Language	Result	Execution time	Memory
739685		asdfgrace	Global Warming (CEOI18_glo)	C++17	100 / 100	56 ms	4556 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 {
  int n, k;
  vector<int> a;
 
  void run() {
    cin >> n >> k;
    a.resize(n);
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
    }
    
    vector<int> lis(n, INT_MAX), best(n);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int pos = lower_bound(lis.begin(), lis.end(), a[i]) - lis.begin();
      lis[pos] = a[i];
      best[i] = pos + 1;
      ans = max(ans, best[i]);
    }
    
    fill(lis.begin(), lis.end(), INT_MAX);
    for (int i = n - 1; i >= 0; --i) {
      // binary search for first element counted in LDS
      int firstcnt = lower_bound(lis.begin(), lis.end(), -a[i] + k) - lis.begin();
      ans = max(ans, best[i] + firstcnt);
      // binary search for where to add next modified element
      int pos = lower_bound(lis.begin(), lis.end(), -a[i]) - lis.begin();
      lis[pos] = -a[i];
    }
    cout << ans << '\n';
  }
};
 
int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  auto sol = make_unique<S>();
  sol->run();
}

• 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