oj.uz

Submission #814929

# Submission time Handle Problem Language Result Execution time Memory
814929 2023-08-08T11:13:12 Z KoD Radio Towers (IOI22_towers) C++17
100 / 100
 1272 ms 51604 KB 
#include "towers.h"

#include <algorithm>
#include <cassert>
#include <array>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

namespace kod {

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;

using std::begin;
using std::end;

using ll = long long;
constexpr int inf = (1 << 30) - 1;
constexpr ll infll = (1ll << 62) - 1;

template <class F> int binary_search(int ok, int ng, const F& f) {
  while (std::abs(ok - ng) > 1) {
    const int md = (ok + ng) / 2;
    (f(md) ? ok : ng) = md;
  }
  return ok;
}

template <class T>
struct sparse_table {
  sparse_table() = default;

  explicit sparse_table(vector<T> a) {
    const int n = (int)a.size();
    table.push_back(std::move(a));
    for (int d = 1;; ++d) {
      const int m = n - (1 << d) + 1;
      if (m <= 0) break;
      table.emplace_back().reserve(m);
      for (int i = 0; i < m; ++i) {
        table[d].push_back(std::max(table[d - 1][i], table[d - 1][i + (1 << (d - 1))]));
      }
    }
  }

  T range_max(int l, int r) {
    const int d = 31 - __builtin_clz(r - l);
    return std::max(table[d][l], table[d][r - (1 << d)]);
  }

 private:
  vector<vector<T>> table;
};

struct Node {
  int l, r, sum;
};
vector<Node> node = {{0, 0, 0}};
int make_node(Node n) {
  node.push_back(std::move(n));
  return (int)node.size() - 1;
}
int make_leaf(int x) { return make_node({0, 0, x}); }
int make_parent(int l, int r) { return make_node({l, r, node[l].sum + node[r].sum}); }
int add(int u, int i, int x, int l, int r) {
  if (r - l == 1) return make_leaf(x);
  const int m = (l + r) / 2;
  if (i < m) return make_parent(add(node[u].l, i, x, l, m), node[u].r);
  return make_parent(node[u].l, add(node[u].r, i, x, m, r));
}
int fold(int u, int i, int j, int l, int r) {
  if (u == 0) return 0;
  if (j <= l || r <= i) return 0;
  if (i <= l && r <= j) return node[u].sum;
  const int m = (l + r) / 2;
  return fold(node[u].l, i, j, l, m) + fold(node[u].r, i, j, m, r);
}

struct segment_tree {
  struct Data {
    int min, max, up, down;
  };

  segment_tree() = default;

  explicit segment_tree(const vector<int>& H) {
    size = (int)H.size();
    data.resize(2 * size, {inf, -inf, -inf, -inf});
    for (int i = 0; i < size; ++i) data[i + size] = {H[i], H[i], -inf, -inf};
    for (int i = size - 1; i > 0; --i) data[i] = merge(data[2 * i], data[2 * i + 1]);
  }

  Data fold(int l, int r) const {
    l += size;
    r += size;
    Data ret_l = {inf, -inf, -inf, -inf};
    Data ret_r = {inf, -inf, -inf, -inf};
    while (l < r) {
      if (l & 1) ret_l = merge(ret_l, data[l++]);
      if (r & 1) ret_r = merge(data[--r], ret_r);
      l >>= 1;
      r >>= 1;
    }
    return merge(ret_l, ret_r);
  }

 private:
  int size;
  vector<Data> data;

  static Data merge(const Data& l, const Data& r) {
    return {std::min(l.min, r.min), std::max(l.max, r.max), std::max({l.up, r.up, r.max - l.min}),
            std::max({l.down, r.down, l.max - r.min})};
  }
};

int N;
vector<int> H, sortedD, nodeID;
sparse_table<int> tableH, tableD;
sparse_table<pair<int, int>> minH;
segment_tree seg;

void init() {
  tableH = sparse_table(H);
  vector<int> D(N, inf), st;
  for (int i = 0; i < N; ++i) {
    while (!st.empty() && H[st.back()] >= H[i]) st.pop_back();
    if (!st.empty()) {
      int j = st.back();
      D[i] = std::min(D[i], tableH.range_max(j, i + 1) - H[i]);
    }
    st.push_back(i);
  }
  st.clear();
  for (int i = N - 1; i >= 0; --i) {
    while (!st.empty() && H[st.back()] > H[i]) st.pop_back();
    if (!st.empty()) {
      int j = st.back();
      D[i] = std::min(D[i], tableH.range_max(i, j + 1) - H[i]);
    }
    st.push_back(i);
  }
  tableD = sparse_table(D);
  vector<int> ord(N);
  std::iota(begin(ord), end(ord), 0);
  std::sort(begin(ord), end(ord), [&](int i, int j) { return D[i] < D[j]; });
  sortedD.resize(N);
  nodeID.resize(N + 1);
  for (int i = N - 1; i >= 0; --i) {
    const int k = ord[i];
    sortedD[i] = D[k];
    nodeID[i] = add(nodeID[i + 1], k, 1, 0, N);
  }
  vector<pair<int, int>> tmp(N);
  for (int i = 0; i < N; ++i) {
    tmp[i] = {-H[i], i};
  }
  minH = sparse_table(std::move(tmp));
  seg = segment_tree(H);
}

int query(int L, int R, int D) {
  const int id = nodeID[std::lower_bound(begin(sortedD), end(sortedD), D) - begin(sortedD)];
  int n = fold(id, L, R, 0, N);
  int s = L, t = R;
  if (n == 0) {
    n += 1;
    s = t = minH.range_max(L, R).second;
  } else {
    s = binary_search(R, L, [&](int k) { return tableD.range_max(L, k) >= D; }) - 1;
    t = binary_search(L, R, [&](int k) { return tableD.range_max(k, R) >= D; });
  }
  int S = binary_search(L - 1, s, [&](int k) { return tableH.range_max(k, s) >= H[s] + D; }) + 1;
  int T = binary_search(R + 1, t, [&](int k) { return tableH.range_max(t, k) >= H[t] + D; }) - 1;
  // cerr << L << ' ' << S << ' ' << s << ' ' << t << ' ' << T << ' ' << R << endl;
  return n + (seg.fold(L, S).up >= D) + (seg.fold(T, R).down >= D);
}

}  // namespace kod

void init(int N, std::vector<int> H) {
  kod::N = N;
  kod::H = std::move(H);
  kod::init();
}

int max_towers(int L, int R, int D) { return kod::query(L, R + 1, D); }

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 29624 KB Output is correct
2 Correct 751 ms 51480 KB Output is correct
3 Correct 628 ms 51580 KB Output is correct
4 Correct 740 ms 51500 KB Output is correct
5 Correct 707 ms 51596 KB Output is correct
6 Correct 790 ms 51536 KB Output is correct
7 Correct 775 ms 51476 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 972 KB Output is correct
10 Correct 1 ms 1040 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 2 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 2 ms 972 KB Output is correct
8 Correct 2 ms 1040 KB Output is correct
9 Correct 1 ms 972 KB Output is correct
10 Correct 2 ms 1040 KB Output is correct
11 Correct 1 ms 1040 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 1 ms 972 KB Output is correct
14 Correct 1 ms 1000 KB Output is correct
15 Correct 1 ms 972 KB Output is correct
16 Correct 1 ms 972 KB Output is correct
17 Correct 1 ms 972 KB Output is correct
18 Correct 1 ms 972 KB Output is correct
19 Correct 1 ms 1040 KB Output is correct
20 Correct 1 ms 972 KB Output is correct
21 Correct 1 ms 972 KB Output is correct
22 Correct 1 ms 972 KB Output is correct
23 Correct 1 ms 1040 KB Output is correct
24 Correct 1 ms 972 KB Output is correct
25 Correct 1 ms 592 KB Output is correct
26 Correct 1 ms 972 KB Output is correct
27 Correct 1 ms 972 KB Output is correct
28 Correct 1 ms 972 KB Output is correct
29 Correct 1 ms 972 KB Output is correct
30 Correct 1 ms 972 KB Output is correct
31 Correct 1 ms 972 KB Output is correct
32 Correct 1 ms 972 KB Output is correct
33 Correct 1 ms 1040 KB Output is correct
34 Correct 1 ms 972 KB Output is correct
35 Correct 1 ms 972 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 2 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 2 ms 972 KB Output is correct
8 Correct 2 ms 1040 KB Output is correct
9 Correct 1 ms 972 KB Output is correct
10 Correct 2 ms 1040 KB Output is correct
11 Correct 1 ms 1040 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 1 ms 972 KB Output is correct
14 Correct 1 ms 1000 KB Output is correct
15 Correct 1 ms 972 KB Output is correct
16 Correct 1 ms 972 KB Output is correct
17 Correct 1 ms 972 KB Output is correct
18 Correct 1 ms 972 KB Output is correct
19 Correct 1 ms 1040 KB Output is correct
20 Correct 1 ms 972 KB Output is correct
21 Correct 1 ms 972 KB Output is correct
22 Correct 1 ms 972 KB Output is correct
23 Correct 1 ms 1040 KB Output is correct
24 Correct 1 ms 972 KB Output is correct
25 Correct 1 ms 592 KB Output is correct
26 Correct 1 ms 972 KB Output is correct
27 Correct 1 ms 972 KB Output is correct
28 Correct 1 ms 972 KB Output is correct
29 Correct 1 ms 972 KB Output is correct
30 Correct 1 ms 972 KB Output is correct
31 Correct 1 ms 972 KB Output is correct
32 Correct 1 ms 972 KB Output is correct
33 Correct 1 ms 1040 KB Output is correct
34 Correct 1 ms 972 KB Output is correct
35 Correct 1 ms 972 KB Output is correct
36 Correct 55 ms 34300 KB Output is correct
37 Correct 80 ms 51076 KB Output is correct
38 Correct 76 ms 51108 KB Output is correct
39 Correct 88 ms 51236 KB Output is correct
40 Correct 89 ms 51192 KB Output is correct
41 Correct 82 ms 51132 KB Output is correct
42 Correct 78 ms 51064 KB Output is correct
43 Correct 72 ms 51508 KB Output is correct
44 Correct 66 ms 51572 KB Output is correct
45 Correct 76 ms 51320 KB Output is correct
46 Correct 71 ms 51348 KB Output is correct
47 Correct 80 ms 51096 KB Output is correct
48 Correct 81 ms 51080 KB Output is correct
49 Correct 80 ms 51192 KB Output is correct
50 Correct 71 ms 51556 KB Output is correct
51 Correct 65 ms 51572 KB Output is correct
52 Correct 76 ms 51144 KB Output is correct
53 Correct 91 ms 51064 KB Output is correct
54 Correct 91 ms 51084 KB Output is correct
55 Correct 73 ms 51532 KB Output is correct
56 Correct 65 ms 51328 KB Output is correct
57 Correct 72 ms 49376 KB Output is correct
58 Correct 77 ms 51080 KB Output is correct
59 Correct 74 ms 51052 KB Output is correct
60 Correct 84 ms 51212 KB Output is correct
61 Correct 77 ms 51152 KB Output is correct
62 Correct 83 ms 51064 KB Output is correct
63 Correct 80 ms 51116 KB Output is correct
64 Correct 65 ms 51564 KB Output is correct
65 Correct 68 ms 51572 KB Output is correct
66 Correct 65 ms 51352 KB Output is correct
67 Correct 67 ms 51504 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 819 ms 50660 KB Output is correct
2 Correct 1043 ms 51076 KB Output is correct
3 Correct 987 ms 51080 KB Output is correct
4 Correct 1026 ms 51052 KB Output is correct
5 Correct 1028 ms 51172 KB Output is correct
6 Correct 1084 ms 51096 KB Output is correct
7 Correct 1038 ms 51164 KB Output is correct
8 Correct 824 ms 51560 KB Output is correct
9 Correct 919 ms 51488 KB Output is correct
10 Correct 903 ms 51400 KB Output is correct
11 Correct 893 ms 51588 KB Output is correct
12 Correct 983 ms 51528 KB Output is correct
13 Correct 827 ms 51532 KB Output is correct
14 Correct 0 ms 208 KB Output is correct
15 Correct 1 ms 972 KB Output is correct
16 Correct 1 ms 972 KB Output is correct
17 Correct 75 ms 51184 KB Output is correct
18 Correct 84 ms 51200 KB Output is correct
19 Correct 81 ms 51076 KB Output is correct
20 Correct 70 ms 51552 KB Output is correct
21 Correct 76 ms 51552 KB Output is correct
22 Correct 76 ms 51212 KB Output is correct
23 Correct 80 ms 51144 KB Output is correct
24 Correct 76 ms 51144 KB Output is correct
25 Correct 70 ms 51532 KB Output is correct
26 Correct 79 ms 51276 KB Output is correct
27 Correct 2 ms 980 KB Output is correct
28 Correct 1 ms 972 KB Output is correct
29 Correct 1 ms 972 KB Output is correct
30 Correct 1 ms 1040 KB Output is correct
31 Correct 1 ms 1040 KB Output is correct
32 Correct 1 ms 972 KB Output is correct
33 Correct 2 ms 972 KB Output is correct
34 Correct 1 ms 972 KB Output is correct
35 Correct 1 ms 1004 KB Output is correct
36 Correct 1 ms 1040 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 11020 KB Output is correct
2 Correct 726 ms 51080 KB Output is correct
3 Correct 727 ms 51084 KB Output is correct
4 Correct 715 ms 51124 KB Output is correct
5 Correct 693 ms 51164 KB Output is correct
6 Correct 687 ms 51168 KB Output is correct
7 Correct 784 ms 51080 KB Output is correct
8 Correct 811 ms 51592 KB Output is correct
9 Correct 773 ms 51584 KB Output is correct
10 Correct 743 ms 51460 KB Output is correct
11 Correct 717 ms 51404 KB Output is correct
12 Correct 76 ms 51072 KB Output is correct
13 Correct 85 ms 51128 KB Output is correct
14 Correct 76 ms 51208 KB Output is correct
15 Correct 72 ms 51480 KB Output is correct
16 Correct 66 ms 51300 KB Output is correct
17 Correct 73 ms 49340 KB Output is correct
18 Correct 84 ms 51076 KB Output is correct
19 Correct 80 ms 51116 KB Output is correct
20 Correct 77 ms 51096 KB Output is correct
21 Correct 77 ms 51088 KB Output is correct
22 Correct 76 ms 51128 KB Output is correct
23 Correct 83 ms 51076 KB Output is correct
24 Correct 67 ms 51504 KB Output is correct
25 Correct 64 ms 51584 KB Output is correct
26 Correct 64 ms 51300 KB Output is correct
27 Correct 66 ms 51468 KB Output is correct
28 Correct 1 ms 972 KB Output is correct
29 Correct 1 ms 972 KB Output is correct
30 Correct 1 ms 972 KB Output is correct
31 Correct 1 ms 972 KB Output is correct
32 Correct 1 ms 972 KB Output is correct
33 Correct 1 ms 604 KB Output is correct
34 Correct 1 ms 972 KB Output is correct
35 Correct 1 ms 972 KB Output is correct
36 Correct 1 ms 972 KB Output is correct
37 Correct 1 ms 972 KB Output is correct
38 Correct 1 ms 972 KB Output is correct
39 Correct 1 ms 972 KB Output is correct
40 Correct 1 ms 972 KB Output is correct
41 Correct 1 ms 972 KB Output is correct
42 Correct 1 ms 972 KB Output is correct
43 Correct 1 ms 972 KB Output is correct

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 2 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 2 ms 972 KB Output is correct
8 Correct 2 ms 1040 KB Output is correct
9 Correct 1 ms 972 KB Output is correct
10 Correct 2 ms 1040 KB Output is correct
11 Correct 1 ms 1040 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 1 ms 972 KB Output is correct
14 Correct 1 ms 1000 KB Output is correct
15 Correct 1 ms 972 KB Output is correct
16 Correct 1 ms 972 KB Output is correct
17 Correct 1 ms 972 KB Output is correct
18 Correct 1 ms 972 KB Output is correct
19 Correct 1 ms 1040 KB Output is correct
20 Correct 1 ms 972 KB Output is correct
21 Correct 1 ms 972 KB Output is correct
22 Correct 1 ms 972 KB Output is correct
23 Correct 1 ms 1040 KB Output is correct
24 Correct 1 ms 972 KB Output is correct
25 Correct 1 ms 592 KB Output is correct
26 Correct 1 ms 972 KB Output is correct
27 Correct 1 ms 972 KB Output is correct
28 Correct 1 ms 972 KB Output is correct
29 Correct 1 ms 972 KB Output is correct
30 Correct 1 ms 972 KB Output is correct
31 Correct 1 ms 972 KB Output is correct
32 Correct 1 ms 972 KB Output is correct
33 Correct 1 ms 1040 KB Output is correct
34 Correct 1 ms 972 KB Output is correct
35 Correct 1 ms 972 KB Output is correct
36 Correct 55 ms 34300 KB Output is correct
37 Correct 80 ms 51076 KB Output is correct
38 Correct 76 ms 51108 KB Output is correct
39 Correct 88 ms 51236 KB Output is correct
40 Correct 89 ms 51192 KB Output is correct
41 Correct 82 ms 51132 KB Output is correct
42 Correct 78 ms 51064 KB Output is correct
43 Correct 72 ms 51508 KB Output is correct
44 Correct 66 ms 51572 KB Output is correct
45 Correct 76 ms 51320 KB Output is correct
46 Correct 71 ms 51348 KB Output is correct
47 Correct 80 ms 51096 KB Output is correct
48 Correct 81 ms 51080 KB Output is correct
49 Correct 80 ms 51192 KB Output is correct
50 Correct 71 ms 51556 KB Output is correct
51 Correct 65 ms 51572 KB Output is correct
52 Correct 76 ms 51144 KB Output is correct
53 Correct 91 ms 51064 KB Output is correct
54 Correct 91 ms 51084 KB Output is correct
55 Correct 73 ms 51532 KB Output is correct
56 Correct 65 ms 51328 KB Output is correct
57 Correct 72 ms 49376 KB Output is correct
58 Correct 77 ms 51080 KB Output is correct
59 Correct 74 ms 51052 KB Output is correct
60 Correct 84 ms 51212 KB Output is correct
61 Correct 77 ms 51152 KB Output is correct
62 Correct 83 ms 51064 KB Output is correct
63 Correct 80 ms 51116 KB Output is correct
64 Correct 65 ms 51564 KB Output is correct
65 Correct 68 ms 51572 KB Output is correct
66 Correct 65 ms 51352 KB Output is correct
67 Correct 67 ms 51504 KB Output is correct
68 Correct 819 ms 50660 KB Output is correct
69 Correct 1043 ms 51076 KB Output is correct
70 Correct 987 ms 51080 KB Output is correct
71 Correct 1026 ms 51052 KB Output is correct
72 Correct 1028 ms 51172 KB Output is correct
73 Correct 1084 ms 51096 KB Output is correct
74 Correct 1038 ms 51164 KB Output is correct
75 Correct 824 ms 51560 KB Output is correct
76 Correct 919 ms 51488 KB Output is correct
77 Correct 903 ms 51400 KB Output is correct
78 Correct 893 ms 51588 KB Output is correct
79 Correct 983 ms 51528 KB Output is correct
80 Correct 827 ms 51532 KB Output is correct
81 Correct 0 ms 208 KB Output is correct
82 Correct 1 ms 972 KB Output is correct
83 Correct 1 ms 972 KB Output is correct
84 Correct 75 ms 51184 KB Output is correct
85 Correct 84 ms 51200 KB Output is correct
86 Correct 81 ms 51076 KB Output is correct
87 Correct 70 ms 51552 KB Output is correct
88 Correct 76 ms 51552 KB Output is correct
89 Correct 76 ms 51212 KB Output is correct
90 Correct 80 ms 51144 KB Output is correct
91 Correct 76 ms 51144 KB Output is correct
92 Correct 70 ms 51532 KB Output is correct
93 Correct 79 ms 51276 KB Output is correct
94 Correct 2 ms 980 KB Output is correct
95 Correct 1 ms 972 KB Output is correct
96 Correct 1 ms 972 KB Output is correct
97 Correct 1 ms 1040 KB Output is correct
98 Correct 1 ms 1040 KB Output is correct
99 Correct 1 ms 972 KB Output is correct
100 Correct 2 ms 972 KB Output is correct
101 Correct 1 ms 972 KB Output is correct
102 Correct 1 ms 1004 KB Output is correct
103 Correct 1 ms 1040 KB Output is correct
104 Correct 825 ms 45028 KB Output is correct
105 Correct 883 ms 51136 KB Output is correct
106 Correct 938 ms 51184 KB Output is correct
107 Correct 767 ms 51064 KB Output is correct
108 Correct 847 ms 51188 KB Output is correct
109 Correct 961 ms 51136 KB Output is correct
110 Correct 897 ms 51076 KB Output is correct
111 Correct 708 ms 51452 KB Output is correct
112 Correct 660 ms 51496 KB Output is correct
113 Correct 687 ms 51300 KB Output is correct
114 Correct 713 ms 51604 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 29624 KB Output is correct
2 Correct 751 ms 51480 KB Output is correct
3 Correct 628 ms 51580 KB Output is correct
4 Correct 740 ms 51500 KB Output is correct
5 Correct 707 ms 51596 KB Output is correct
6 Correct 790 ms 51536 KB Output is correct
7 Correct 775 ms 51476 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 972 KB Output is correct
10 Correct 1 ms 1040 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 972 KB Output is correct
13 Correct 2 ms 972 KB Output is correct
14 Correct 1 ms 972 KB Output is correct
15 Correct 1 ms 972 KB Output is correct
16 Correct 1 ms 972 KB Output is correct
17 Correct 2 ms 972 KB Output is correct
18 Correct 2 ms 1040 KB Output is correct
19 Correct 1 ms 972 KB Output is correct
20 Correct 2 ms 1040 KB Output is correct
21 Correct 1 ms 1040 KB Output is correct
22 Correct 0 ms 208 KB Output is correct
23 Correct 1 ms 972 KB Output is correct
24 Correct 1 ms 1000 KB Output is correct
25 Correct 1 ms 972 KB Output is correct
26 Correct 1 ms 972 KB Output is correct
27 Correct 1 ms 972 KB Output is correct
28 Correct 1 ms 972 KB Output is correct
29 Correct 1 ms 1040 KB Output is correct
30 Correct 1 ms 972 KB Output is correct
31 Correct 1 ms 972 KB Output is correct
32 Correct 1 ms 972 KB Output is correct
33 Correct 1 ms 1040 KB Output is correct
34 Correct 1 ms 972 KB Output is correct
35 Correct 1 ms 592 KB Output is correct
36 Correct 1 ms 972 KB Output is correct
37 Correct 1 ms 972 KB Output is correct
38 Correct 1 ms 972 KB Output is correct
39 Correct 1 ms 972 KB Output is correct
40 Correct 1 ms 972 KB Output is correct
41 Correct 1 ms 972 KB Output is correct
42 Correct 1 ms 972 KB Output is correct
43 Correct 1 ms 1040 KB Output is correct
44 Correct 1 ms 972 KB Output is correct
45 Correct 1 ms 972 KB Output is correct
46 Correct 55 ms 34300 KB Output is correct
47 Correct 80 ms 51076 KB Output is correct
48 Correct 76 ms 51108 KB Output is correct
49 Correct 88 ms 51236 KB Output is correct
50 Correct 89 ms 51192 KB Output is correct
51 Correct 82 ms 51132 KB Output is correct
52 Correct 78 ms 51064 KB Output is correct
53 Correct 72 ms 51508 KB Output is correct
54 Correct 66 ms 51572 KB Output is correct
55 Correct 76 ms 51320 KB Output is correct
56 Correct 71 ms 51348 KB Output is correct
57 Correct 80 ms 51096 KB Output is correct
58 Correct 81 ms 51080 KB Output is correct
59 Correct 80 ms 51192 KB Output is correct
60 Correct 71 ms 51556 KB Output is correct
61 Correct 65 ms 51572 KB Output is correct
62 Correct 76 ms 51144 KB Output is correct
63 Correct 91 ms 51064 KB Output is correct
64 Correct 91 ms 51084 KB Output is correct
65 Correct 73 ms 51532 KB Output is correct
66 Correct 65 ms 51328 KB Output is correct
67 Correct 72 ms 49376 KB Output is correct
68 Correct 77 ms 51080 KB Output is correct
69 Correct 74 ms 51052 KB Output is correct
70 Correct 84 ms 51212 KB Output is correct
71 Correct 77 ms 51152 KB Output is correct
72 Correct 83 ms 51064 KB Output is correct
73 Correct 80 ms 51116 KB Output is correct
74 Correct 65 ms 51564 KB Output is correct
75 Correct 68 ms 51572 KB Output is correct
76 Correct 65 ms 51352 KB Output is correct
77 Correct 67 ms 51504 KB Output is correct
78 Correct 819 ms 50660 KB Output is correct
79 Correct 1043 ms 51076 KB Output is correct
80 Correct 987 ms 51080 KB Output is correct
81 Correct 1026 ms 51052 KB Output is correct
82 Correct 1028 ms 51172 KB Output is correct
83 Correct 1084 ms 51096 KB Output is correct
84 Correct 1038 ms 51164 KB Output is correct
85 Correct 824 ms 51560 KB Output is correct
86 Correct 919 ms 51488 KB Output is correct
87 Correct 903 ms 51400 KB Output is correct
88 Correct 893 ms 51588 KB Output is correct
89 Correct 983 ms 51528 KB Output is correct
90 Correct 827 ms 51532 KB Output is correct
91 Correct 0 ms 208 KB Output is correct
92 Correct 1 ms 972 KB Output is correct
93 Correct 1 ms 972 KB Output is correct
94 Correct 75 ms 51184 KB Output is correct
95 Correct 84 ms 51200 KB Output is correct
96 Correct 81 ms 51076 KB Output is correct
97 Correct 70 ms 51552 KB Output is correct
98 Correct 76 ms 51552 KB Output is correct
99 Correct 76 ms 51212 KB Output is correct
100 Correct 80 ms 51144 KB Output is correct
101 Correct 76 ms 51144 KB Output is correct
102 Correct 70 ms 51532 KB Output is correct
103 Correct 79 ms 51276 KB Output is correct
104 Correct 2 ms 980 KB Output is correct
105 Correct 1 ms 972 KB Output is correct
106 Correct 1 ms 972 KB Output is correct
107 Correct 1 ms 1040 KB Output is correct
108 Correct 1 ms 1040 KB Output is correct
109 Correct 1 ms 972 KB Output is correct
110 Correct 2 ms 972 KB Output is correct
111 Correct 1 ms 972 KB Output is correct
112 Correct 1 ms 1004 KB Output is correct
113 Correct 1 ms 1040 KB Output is correct
114 Correct 160 ms 11020 KB Output is correct
115 Correct 726 ms 51080 KB Output is correct
116 Correct 727 ms 51084 KB Output is correct
117 Correct 715 ms 51124 KB Output is correct
118 Correct 693 ms 51164 KB Output is correct
119 Correct 687 ms 51168 KB Output is correct
120 Correct 784 ms 51080 KB Output is correct
121 Correct 811 ms 51592 KB Output is correct
122 Correct 773 ms 51584 KB Output is correct
123 Correct 743 ms 51460 KB Output is correct
124 Correct 717 ms 51404 KB Output is correct
125 Correct 76 ms 51072 KB Output is correct
126 Correct 85 ms 51128 KB Output is correct
127 Correct 76 ms 51208 KB Output is correct
128 Correct 72 ms 51480 KB Output is correct
129 Correct 66 ms 51300 KB Output is correct
130 Correct 73 ms 49340 KB Output is correct
131 Correct 84 ms 51076 KB Output is correct
132 Correct 80 ms 51116 KB Output is correct
133 Correct 77 ms 51096 KB Output is correct
134 Correct 77 ms 51088 KB Output is correct
135 Correct 76 ms 51128 KB Output is correct
136 Correct 83 ms 51076 KB Output is correct
137 Correct 67 ms 51504 KB Output is correct
138 Correct 64 ms 51584 KB Output is correct
139 Correct 64 ms 51300 KB Output is correct
140 Correct 66 ms 51468 KB Output is correct
141 Correct 1 ms 972 KB Output is correct
142 Correct 1 ms 972 KB Output is correct
143 Correct 1 ms 972 KB Output is correct
144 Correct 1 ms 972 KB Output is correct
145 Correct 1 ms 972 KB Output is correct
146 Correct 1 ms 604 KB Output is correct
147 Correct 1 ms 972 KB Output is correct
148 Correct 1 ms 972 KB Output is correct
149 Correct 1 ms 972 KB Output is correct
150 Correct 1 ms 972 KB Output is correct
151 Correct 1 ms 972 KB Output is correct
152 Correct 1 ms 972 KB Output is correct
153 Correct 1 ms 972 KB Output is correct
154 Correct 1 ms 972 KB Output is correct
155 Correct 1 ms 972 KB Output is correct
156 Correct 1 ms 972 KB Output is correct
157 Correct 825 ms 45028 KB Output is correct
158 Correct 883 ms 51136 KB Output is correct
159 Correct 938 ms 51184 KB Output is correct
160 Correct 767 ms 51064 KB Output is correct
161 Correct 847 ms 51188 KB Output is correct
162 Correct 961 ms 51136 KB Output is correct
163 Correct 897 ms 51076 KB Output is correct
164 Correct 708 ms 51452 KB Output is correct
165 Correct 660 ms 51496 KB Output is correct
166 Correct 687 ms 51300 KB Output is correct
167 Correct 713 ms 51604 KB Output is correct
168 Correct 0 ms 208 KB Output is correct
169 Correct 567 ms 17328 KB Output is correct
170 Correct 1180 ms 51196 KB Output is correct
171 Correct 1195 ms 51188 KB Output is correct
172 Correct 1272 ms 51076 KB Output is correct
173 Correct 1030 ms 51156 KB Output is correct
174 Correct 1119 ms 51080 KB Output is correct
175 Correct 1238 ms 51180 KB Output is correct
176 Correct 762 ms 51496 KB Output is correct
177 Correct 779 ms 51464 KB Output is correct
178 Correct 960 ms 51516 KB Output is correct
179 Correct 925 ms 51256 KB Output is correct