oj.uz

Submission #397478

# Submission time Handle Problem Language Result Execution time Memory
397478 2021-05-02T09:40:27 Z ollel Global Warming (CEOI18_glo) C++14
38 / 100
 548 ms 15288 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 > 10000) {
    int ans = test(arr);
    cout << ans;
  } else {
    int ans = test(arr);

    rep(end, 0, n) {
      arr[end] -= x;
      ans = max(ans, test(arr));
    }

    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 204 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 204 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 2 ms 204 KB Output is correct
13 Correct 2 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #3
13.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 204 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 2 ms 204 KB Output is correct
13 Correct 2 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 537 ms 344 KB Output is correct
20 Correct 524 ms 364 KB Output is correct
21 Correct 548 ms 452 KB Output is correct
22 Correct 520 ms 364 KB Output is correct
23 Correct 286 ms 332 KB Output is correct
24 Correct 302 ms 332 KB Output is correct
25 Correct 334 ms 464 KB Output is correct
26 Correct 442 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 15204 KB Output is correct
2 Correct 407 ms 15288 KB Output is correct
3 Correct 418 ms 15248 KB Output is correct
4 Correct 455 ms 15184 KB Output is correct
5 Correct 183 ms 10436 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 3936 KB Output is correct
2 Correct 80 ms 3908 KB Output is correct
3 Correct 79 ms 3944 KB Output is correct
4 Incorrect 42 ms 2812 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 195 ms 7604 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 204 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 2 ms 204 KB Output is correct
13 Correct 2 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 537 ms 344 KB Output is correct
20 Correct 524 ms 364 KB Output is correct
21 Correct 548 ms 452 KB Output is correct
22 Correct 520 ms 364 KB Output is correct
23 Correct 286 ms 332 KB Output is correct
24 Correct 302 ms 332 KB Output is correct
25 Correct 334 ms 464 KB Output is correct
26 Correct 442 ms 348 KB Output is correct
27 Correct 436 ms 15204 KB Output is correct
28 Correct 407 ms 15288 KB Output is correct
29 Correct 418 ms 15248 KB Output is correct
30 Correct 455 ms 15184 KB Output is correct
31 Correct 183 ms 10436 KB Output is correct
32 Correct 128 ms 3936 KB Output is correct
33 Correct 80 ms 3908 KB Output is correct
34 Correct 79 ms 3944 KB Output is correct
35 Incorrect 42 ms 2812 KB Output isn't correct
36 Halted 0 ms 0 KB -