oj.uz

Submission #397513

# Submission time Handle Problem Language Result Execution time Memory
397513 2021-05-02T10:17:39 Z ollel Global Warming (CEOI18_glo) C++17
10 / 100
 1094 ms 27928 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back

typedef vector<int> vi;
typedef long long ll;

class SegTree {
public:
  vi tr; int n;

  int l(int x) {return (x<<1);}
  int r(int x) {return (x<<1)|1;}

  int combine(int a, int b) {return max(a, b);}

  void build(int i, int L, int R, vi& arr) {
    if (L == R) tr[i] = arr[L];
    else {
      int mid = (L + R) / 2;
      build(l(i), L, mid, arr);
      build(r(i), mid + 1, R, arr);
      tr[i] = combine(tr[l(i)], tr[r(i)]);
    }
  }

  void build(vi &arr) {
    build(1, 0, n - 1, arr);
  }

  SegTree(vi &arr) {
    n = arr.size();
    tr.resize(4*n);
    this->build(arr);
  }

  int query(int i, int a, int b, int L, int R) {
    if (b < a) return 0;
    if (L > b || R < a) return 0;
    if (L >= a && R <= b) return tr[i];
    int mid = (L + R) / 2;
    return combine(
      query(l(i), a, b, L, mid),
      query(r(i), a, b, mid + 1, R));
  }

  int query(int i, int j) {
    return query(1, i, j, 0, n - 1);
  }

  void update(int i, int a, int L, int R, int v) {
    if (a < L || a > R) return;
    if (L == R) {tr[i] = v; return;}
    int mid = (L + R) / 2;
    update(l(i), a, L, mid, v);
    update(r(i), a, mid + 1, R, v);
    tr[i] = combine(tr[l(i)], tr[r(i)]);
  }

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

int n, x;
vi arr;
vi LIS, LDS;
map<int,int> cmpr;
vi vals;


void prep(vi&arr) {
  LIS.resize(n); LDS.resize(n); vals.resize(n);

  rep(i,0,n) vals[i] = arr[i];
  rep(i,0,n) vals.pb(vals[i] - x);
  sort(vals.begin(), vals.end());
  rep(i,0,2*n) {
    if (cmpr.find(vals[i]) == cmpr.end()) cmpr.insert({vals[i], i});
  }

  vi trarr(2*n, 0);
  SegTree st(trarr);
  rep(i,0,n) {
    int V = cmpr[arr[i]];
    int ans = st.query(0, V - 1) + 1;
    LIS[i] = ans;
    if (st.query(V, V) < ans) st.update(V, ans);
  }

  SegTree std(trarr);
  for (int i = n - 1; i >= 0; i--) {
    int V = cmpr[arr[i]];
    int ans = std.query(V + 1, 2*n - 1) + 1;
    LDS[i] = ans;
    if (std.query(V, V) < ans) std.update(V, ans);
  }
}

void finish() {
  int ans = LIS[n - 1];
  // vi revcmpr(n);
  // for (auto &i : cmpr) revcmpr[i.second] = i.first;
  vi trarr(2*n, 0);
  SegTree st(trarr);
  for (int i = n - 1; i >= 0; i--) {
    int V = cmpr[arr[i]];
    auto mini = lower_bound(vals.begin(), vals.end(), arr[i] - x);
    int M = *mini;
    M = cmpr[M];

    int best = st.query(M + 1, n - 1) + LIS[i];
    ans = max(ans, best);

    st.update(V, LDS[i]);
  }
  cout << ans << endl;
}

int main()
{
  cin >> n >> x;
  arr.resize(n);
  rep(i,0,n) cin>>arr[i];

  prep(arr);
  finish();
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1094 ms 27704 KB Output is correct
2 Correct 1024 ms 27756 KB Output is correct
3 Correct 1088 ms 27928 KB Output is correct
4 Correct 1036 ms 27800 KB Output is correct
5 Correct 415 ms 23080 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 9636 KB Output is correct
2 Correct 203 ms 9624 KB Output is correct
3 Correct 210 ms 9508 KB Output is correct
4 Incorrect 105 ms 7208 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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

Subtask #7
0 / 25.0

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