oj.uz

Submission #625467

# Submission time Handle Problem Language Result Execution time Memory
625467 2022-08-10T12:05:56 Z model_code Radio Towers (IOI22_towers) C++17
27 / 100
 4000 ms 8568 KB 
// time_limit/solution-o-ans.cpp
#ifndef ATCODER_INTERNAL_BITOP_HPP
#define ATCODER_INTERNAL_BITOP_HPP 1

#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
constexpr int bsf_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder

#endif  // ATCODER_INTERNAL_BITOP_HPP

#ifndef ATCODER_SEGTREE_HPP
#define ATCODER_SEGTREE_HPP 1

#include <algorithm>
#include <cassert>
#include <vector>

namespace atcoder {

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
    explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() const { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) const {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) const {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder

#endif  // ATCODER_SEGTREE_HPP

#include "towers.h"

#include <bits/stdc++.h>
using namespace std;

struct Node {
  int max;
  int min;
  int max_right_min_left;
  int max_left_min_right;
};

typedef optional<Node> OptionalNode;

OptionalNode Empty() {
  return {};
}

OptionalNode Merge(OptionalNode l, OptionalNode r) {
  if (!l.has_value()) {
    return r;
  }
  if (!r.has_value()) {
    return l;
  }
  return (Node) {
    max(l.value().max, r.value().max),
    min(l.value().min, r.value().min),
    max(max(l.value().max_right_min_left, r.value().max_right_min_left),
        r.value().max - l.value().min),
    max(max(l.value().max_left_min_right, r.value().max_left_min_right),
        l.value().max - r.value().min)
  };
}

typedef atcoder::segtree<OptionalNode, Merge, Empty> Segtree;

int N;
vector<int> H;
Segtree st;

void init(int _N, std::vector<int> _H) {
  N = _N;
  H = _H;
  st = Segtree(N);
  for (int i = 0; i < N; ++i) {
    st.set(i, (Node) {H[i], H[i], INT_MIN, INT_MIN});
  }
}

int max_towers(int L, int R, int D) {
  int answer = 1;
  int now = L;
  for (bool up = true; now < R; up = !up) {
    if (up) {
      int min_tall = st.max_right(now, [&] (OptionalNode node) {
        return !node.has_value() || node.value().max_right_min_left < D;
      });
      if (min_tall <= R) {
        now = min_tall;
      } else {
        now = R;
      }
    } else {
      int min_choose = st.max_right(now, [&] (OptionalNode node) {
        return !node.has_value() || node.value().max_left_min_right < D;
      });
      if (min_choose <= R) {
        now = min_choose;
        ++answer;
      } else {
        now = R;
      }
    }
  }
  return answer;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 4648 KB Output is correct
2 Correct 1136 ms 8476 KB Output is correct
3 Correct 1237 ms 8476 KB Output is correct
4 Correct 1100 ms 8472 KB Output is correct
5 Correct 1363 ms 8480 KB Output is correct
6 Correct 1084 ms 8528 KB Output is correct
7 Correct 956 ms 8480 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 444 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 432 KB Output is correct
6 Correct 2 ms 440 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 1 ms 440 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 436 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 1 ms 436 KB Output is correct
22 Correct 2 ms 336 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 2 ms 336 KB Output is correct
27 Correct 1 ms 440 KB Output is correct
28 Correct 2 ms 336 KB Output is correct
29 Correct 2 ms 336 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 2 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 2 ms 436 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 444 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 432 KB Output is correct
6 Correct 2 ms 440 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 1 ms 440 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 436 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 1 ms 436 KB Output is correct
22 Correct 2 ms 336 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 2 ms 336 KB Output is correct
27 Correct 1 ms 440 KB Output is correct
28 Correct 2 ms 336 KB Output is correct
29 Correct 2 ms 336 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 2 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 2 ms 436 KB Output is correct
36 Correct 42 ms 4836 KB Output is correct
37 Correct 64 ms 8480 KB Output is correct
38 Correct 65 ms 8512 KB Output is correct
39 Correct 67 ms 8496 KB Output is correct
40 Correct 64 ms 8476 KB Output is correct
41 Correct 67 ms 8488 KB Output is correct
42 Correct 56 ms 8492 KB Output is correct
43 Correct 60 ms 8520 KB Output is correct
44 Correct 53 ms 8496 KB Output is correct
45 Correct 65 ms 8492 KB Output is correct
46 Correct 68 ms 8484 KB Output is correct
47 Correct 56 ms 8500 KB Output is correct
48 Correct 61 ms 8476 KB Output is correct
49 Correct 67 ms 8480 KB Output is correct
50 Correct 57 ms 8468 KB Output is correct
51 Correct 58 ms 8488 KB Output is correct
52 Correct 59 ms 8480 KB Output is correct
53 Correct 68 ms 8504 KB Output is correct
54 Correct 52 ms 8464 KB Output is correct
55 Correct 59 ms 8480 KB Output is correct
56 Correct 71 ms 8472 KB Output is correct
57 Correct 68 ms 8356 KB Output is correct
58 Correct 67 ms 8548 KB Output is correct
59 Correct 55 ms 8496 KB Output is correct
60 Correct 77 ms 8488 KB Output is correct
61 Correct 71 ms 8524 KB Output is correct
62 Correct 70 ms 8532 KB Output is correct
63 Correct 59 ms 8472 KB Output is correct
64 Correct 62 ms 8568 KB Output is correct
65 Correct 57 ms 8484 KB Output is correct
66 Correct 56 ms 8480 KB Output is correct
67 Correct 74 ms 8504 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4038 ms 8492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4058 ms 2296 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 444 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 432 KB Output is correct
6 Correct 2 ms 440 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 1 ms 440 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Correct 2 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 436 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 1 ms 436 KB Output is correct
22 Correct 2 ms 336 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 2 ms 336 KB Output is correct
27 Correct 1 ms 440 KB Output is correct
28 Correct 2 ms 336 KB Output is correct
29 Correct 2 ms 336 KB Output is correct
30 Correct 2 ms 384 KB Output is correct
31 Correct 2 ms 384 KB Output is correct
32 Correct 2 ms 384 KB Output is correct
33 Correct 1 ms 384 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 2 ms 436 KB Output is correct
36 Correct 42 ms 4836 KB Output is correct
37 Correct 64 ms 8480 KB Output is correct
38 Correct 65 ms 8512 KB Output is correct
39 Correct 67 ms 8496 KB Output is correct
40 Correct 64 ms 8476 KB Output is correct
41 Correct 67 ms 8488 KB Output is correct
42 Correct 56 ms 8492 KB Output is correct
43 Correct 60 ms 8520 KB Output is correct
44 Correct 53 ms 8496 KB Output is correct
45 Correct 65 ms 8492 KB Output is correct
46 Correct 68 ms 8484 KB Output is correct
47 Correct 56 ms 8500 KB Output is correct
48 Correct 61 ms 8476 KB Output is correct
49 Correct 67 ms 8480 KB Output is correct
50 Correct 57 ms 8468 KB Output is correct
51 Correct 58 ms 8488 KB Output is correct
52 Correct 59 ms 8480 KB Output is correct
53 Correct 68 ms 8504 KB Output is correct
54 Correct 52 ms 8464 KB Output is correct
55 Correct 59 ms 8480 KB Output is correct
56 Correct 71 ms 8472 KB Output is correct
57 Correct 68 ms 8356 KB Output is correct
58 Correct 67 ms 8548 KB Output is correct
59 Correct 55 ms 8496 KB Output is correct
60 Correct 77 ms 8488 KB Output is correct
61 Correct 71 ms 8524 KB Output is correct
62 Correct 70 ms 8532 KB Output is correct
63 Correct 59 ms 8472 KB Output is correct
64 Correct 62 ms 8568 KB Output is correct
65 Correct 57 ms 8484 KB Output is correct
66 Correct 56 ms 8480 KB Output is correct
67 Correct 74 ms 8504 KB Output is correct
68 Execution timed out 4038 ms 8492 KB Time limit exceeded
69 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 4648 KB Output is correct
2 Correct 1136 ms 8476 KB Output is correct
3 Correct 1237 ms 8476 KB Output is correct
4 Correct 1100 ms 8472 KB Output is correct
5 Correct 1363 ms 8480 KB Output is correct
6 Correct 1084 ms 8528 KB Output is correct
7 Correct 956 ms 8480 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 2 ms 444 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 2 ms 432 KB Output is correct
16 Correct 2 ms 440 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 2 ms 336 KB Output is correct
19 Correct 2 ms 336 KB Output is correct
20 Correct 1 ms 440 KB Output is correct
21 Correct 2 ms 336 KB Output is correct
22 Correct 1 ms 208 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 2 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Correct 1 ms 436 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 2 ms 336 KB Output is correct
31 Correct 1 ms 436 KB Output is correct
32 Correct 2 ms 336 KB Output is correct
33 Correct 2 ms 336 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 336 KB Output is correct
36 Correct 2 ms 336 KB Output is correct
37 Correct 1 ms 440 KB Output is correct
38 Correct 2 ms 336 KB Output is correct
39 Correct 2 ms 336 KB Output is correct
40 Correct 2 ms 384 KB Output is correct
41 Correct 2 ms 384 KB Output is correct
42 Correct 2 ms 384 KB Output is correct
43 Correct 1 ms 384 KB Output is correct
44 Correct 1 ms 336 KB Output is correct
45 Correct 2 ms 436 KB Output is correct
46 Correct 42 ms 4836 KB Output is correct
47 Correct 64 ms 8480 KB Output is correct
48 Correct 65 ms 8512 KB Output is correct
49 Correct 67 ms 8496 KB Output is correct
50 Correct 64 ms 8476 KB Output is correct
51 Correct 67 ms 8488 KB Output is correct
52 Correct 56 ms 8492 KB Output is correct
53 Correct 60 ms 8520 KB Output is correct
54 Correct 53 ms 8496 KB Output is correct
55 Correct 65 ms 8492 KB Output is correct
56 Correct 68 ms 8484 KB Output is correct
57 Correct 56 ms 8500 KB Output is correct
58 Correct 61 ms 8476 KB Output is correct
59 Correct 67 ms 8480 KB Output is correct
60 Correct 57 ms 8468 KB Output is correct
61 Correct 58 ms 8488 KB Output is correct
62 Correct 59 ms 8480 KB Output is correct
63 Correct 68 ms 8504 KB Output is correct
64 Correct 52 ms 8464 KB Output is correct
65 Correct 59 ms 8480 KB Output is correct
66 Correct 71 ms 8472 KB Output is correct
67 Correct 68 ms 8356 KB Output is correct
68 Correct 67 ms 8548 KB Output is correct
69 Correct 55 ms 8496 KB Output is correct
70 Correct 77 ms 8488 KB Output is correct
71 Correct 71 ms 8524 KB Output is correct
72 Correct 70 ms 8532 KB Output is correct
73 Correct 59 ms 8472 KB Output is correct
74 Correct 62 ms 8568 KB Output is correct
75 Correct 57 ms 8484 KB Output is correct
76 Correct 56 ms 8480 KB Output is correct
77 Correct 74 ms 8504 KB Output is correct
78 Execution timed out 4038 ms 8492 KB Time limit exceeded
79 Halted 0 ms 0 KB -