oj.uz

Submission #529723

# Submission time Handle Problem Language Result Execution time Memory
529723 2022-02-23T14:31:09 Z Alex_tz307 Global Warming (CEOI18_glo) C++17
27 / 100
 239 ms 6652 KB 
#include <bits/stdc++.h>

using namespace std;

void maxSelf(int &x, int y) {
  if (x < y) {
    x = y;
  }
}

struct ST {
  int n;
  vector<int> t;

  ST(int N) : n(N) {
    int dim = 1;
    while (dim < n) {
      dim *= 2;
    }
    t.resize(dim * 2);
  }

  void reset() {
    for (int &it : t) {
      it = 0;
    }
  }

  void update(int x, int lx, int rx, int pos, int v) {
    if (lx == rx) {
      t[x] = v;
      return;
    }
    int mid = (lx + rx) / 2;
    if (pos <= mid) {
      update(x * 2, lx, mid, pos, v);
    } else {
      update(x * 2 + 1, mid + 1, rx, pos, v);
    }
    t[x] = max(t[x * 2], t[x * 2 + 1]);
  }

  void update(int pos, int v) {
    update(1, 0, n - 1, pos, v);
  }

  int query(int x, int lx, int rx, int st, int dr) {
    if (st <= lx && rx <= dr) {
      return t[x];
    }
    int mid = (lx + rx) / 2, ans = 0;
    if (st <= mid) {
      maxSelf(ans, query(x * 2, lx, mid, st, dr));
    }
    if (mid < dr) {
      maxSelf(ans, query(x * 2 + 1, mid + 1, rx, st, dr));
    }
    return ans;
  }

  int query(int st, int dr) {
    if (dr < st) {
      return 0;
    }
    return query(1, 0, n - 1, st, dr);
  }
};

void testCase() {
  int n, x;
  cin >> n >> x;
  vector<int> a(n);
  for (int &x : a) {
    cin >> x;
  }
  vector<int> v = a;
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  int m = v.size();
  ST t(m);
  vector<int> dp(n);
  auto getIndex = [&](const int &val) -> int {
    return distance(v.begin(), lower_bound(v.begin(), v.end(), val));
  };
  for (int i = n - 1; i >= 0; --i) {
    a[i] = getIndex(a[i]);
    dp[i] = t.query(a[i] + 1, m - 1) + 1;
    t.update(a[i], dp[i]);
  }
  t.reset();
  int ans = *max_element(dp.begin(), dp.end());
  for (int i = 0; i < n; ++i) {
    maxSelf(ans, t.query(0, getIndex(a[i] + x) - 1) + dp[i]);
    int best = t.query(0, a[i] - 1) + 1;
    t.update(a[i], best);
  }
  cout << ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 6648 KB Output is correct
2 Correct 239 ms 6652 KB Output is correct
3 Correct 217 ms 6648 KB Output is correct
4 Correct 192 ms 6648 KB Output is correct
5 Correct 103 ms 4800 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1868 KB Output is correct
2 Correct 47 ms 1860 KB Output is correct
3 Correct 42 ms 1900 KB Output is correct
4 Incorrect 24 ms 1352 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 3396 KB Output is correct
2 Correct 82 ms 3480 KB Output is correct
3 Correct 185 ms 6640 KB Output is correct
4 Correct 89 ms 4852 KB Output is correct
5 Correct 53 ms 3012 KB Output is correct
6 Correct 96 ms 5804 KB Output is correct
7 Correct 108 ms 6416 KB Output is correct
8 Correct 73 ms 3404 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -