oj.uz

Submission #397097

# Submission time Handle Problem Language Result Execution time Memory
397097 2021-05-01T12:03:57 Z ollel Global Warming (CEOI18_glo) C++14
10 / 100
 427 ms 15284 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 (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;

int test(vi&arr) {
  vi vals(n);
  map<int,int> cmpr;
  rep(i,0,n) vals[i] = arr[i];
  sort(vals.begin(), vals.end());
  cmpr.insert({vals[0], 0}); int k = 1;
  rep(i,0,n) {
    if (vals[i] != vals[i - 1]) {cmpr.insert({vals[i], k});k++;}
  }

  vi trarr(n, 0);
  SegTree st(trarr);

  rep(i,0,n) {
    int V = cmpr[arr[i]];
    int ans = st.query(0, V - 1) + 1;
    if (st.query(V, V) < ans) st.update(V, ans);
  }
  return st.query(0, n - 1);
}

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

  if (n > 55) {
    int ans = test(arr);
    cout << ans;
  } else {
    int ans = test(arr);

    rep(start, 0, n) {
      rep(end, start, n) {
        if (start == 0) {
          rep(i,0,end+1)arr[i] -= x;
          ans = max(ans, test(arr));
          rep(i,0,end+1)arr[i] += x;
        } else {
          rep(vcd, 0, start) {
            int change = arr[vcd] + 1 - arr[start];
            if (abs(change) > x) continue;
            rep(i,start,end+1) arr[i] += change;
            ans = max(ans, test(arr));
            rep(i,start,end+1) arr[i] -= change;
          }
        }
      }
    }
    cout << ans;
  }
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 15164 KB Output is correct
2 Correct 419 ms 15044 KB Output is correct
3 Correct 420 ms 15284 KB Output is correct
4 Correct 405 ms 15144 KB Output is correct
5 Correct 167 ms 10412 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 4036 KB Output is correct
2 Correct 76 ms 4008 KB Output is correct
3 Correct 76 ms 3948 KB Output is correct
4 Incorrect 39 ms 2764 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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

Subtask #7
0 / 25.0

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