oj.uz

Submission #397105

# Submission time Handle Problem Language Result Execution time Memory
397105 2021-05-01T12:39:03 Z ollel Global Warming (CEOI18_glo) C++14
25 / 100
 471 ms 15172 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;

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

  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) {

        rep(i,start,end+1)arr[i] -= x;
        ans = max(ans, test(arr));
        rep(i,start,end+1)arr[i] += x;

        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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 189 ms 204 KB Output is correct
13 Correct 19 ms 204 KB Output is correct
14 Correct 190 ms 284 KB Output is correct
15 Correct 128 ms 204 KB Output is correct
16 Correct 109 ms 284 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 3 ms 204 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 189 ms 204 KB Output is correct
13 Correct 19 ms 204 KB Output is correct
14 Correct 190 ms 284 KB Output is correct
15 Correct 128 ms 204 KB Output is correct
16 Correct 109 ms 284 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 3 ms 204 KB Output is correct
19 Incorrect 2 ms 332 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 15168 KB Output is correct
2 Correct 455 ms 15164 KB Output is correct
3 Correct 471 ms 15168 KB Output is correct
4 Correct 411 ms 15172 KB Output is correct
5 Correct 177 ms 10420 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 3960 KB Output is correct
2 Correct 82 ms 3936 KB Output is correct
3 Correct 81 ms 4008 KB Output is correct
4 Incorrect 41 ms 2796 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 189 ms 204 KB Output is correct
13 Correct 19 ms 204 KB Output is correct
14 Correct 190 ms 284 KB Output is correct
15 Correct 128 ms 204 KB Output is correct
16 Correct 109 ms 284 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 3 ms 204 KB Output is correct
19 Incorrect 2 ms 332 KB Output isn't correct
20 Halted 0 ms 0 KB -