oj.uz

Submission #1072357

# Submission time Handle Problem Language Result Execution time Memory
1072357 2024-08-23T17:29:41 Z ventusliberum Global Warming (CEOI18_glo) C++17
0 / 100
 37 ms 4728 KB 
/**
 *    title:  Global Warming
**/
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define si(x) int(x.size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
template <class T, class U> inline bool chmax(T &a, U b) { return (a < b ? a = b, 1 : 0); }
template <class T, class U> inline bool chmin(T &a, U b) { return (b < a ? a = b, 1 : 0); }
template <class T> istream &operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <class T> ostream &operator<<(ostream &os, const vector<T> &v) { rep(i, si(v)) os << (i ? " " : "") << v[i]; return os; }
using ll = long long;
constexpr int inf = 1001001001;
constexpr long long infll = 4004004004004004004LL;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, x;
  cin >> n >> x;
  vector<int> t(n);
  cin >> t;
  vector<int> lis(n, inf), f(n);
  rep(i, n) {
    int j = lower_bound(all(lis), t[i]) - lis.begin();
    f[i] = j;
    j = lower_bound(all(lis), t[i] - x) - lis.begin();
    lis[j] = t[i] - x;
  }
  int ans = si(lis);
  lis.assign(n, inf);
  for (int i = n - 1; i > 0; i--) {
    int j = lower_bound(all(lis), -t[i]) - lis.begin();
    chmax(ans, f[i] + j + 1);
    lis[j] = -t[i];
  }
  cout << ans << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 4728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -