oj.uz

Submission #867940

# Submission time Handle Problem Language Result Execution time Memory
867940 2023-10-29T22:26:16 Z evenvalue Diversity (CEOI21_diversity) C++17
100 / 100
 4178 ms 21256 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

#ifdef evenvalue
  #include "debug.h"
  #define debug(...) print(#__VA_ARGS__, __VA_ARGS__)
#else
  #define debug(...)
#endif

using int64 = long long;
using ld = long double;

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

namespace Read {
int Int() {
  int x;
  cin >> x;
  return x;
}
int64 Int64() {
  int64 x;
  cin >> x;
  return x;
}
char Char() {
  char c;
  cin >> c;
  return c;
}
string String() {
  string s;
  cin >> s;
  return s;
}
double Double() {
  return stod(String());
}
ld LongDouble() {
  return stold(String());
}
template<typename T1, typename T2>
pair<T1, T2> Pair() {
  pair<T1, T2> p;
  cin >> p.first >> p.second;
  return p;
}
template<typename T>
vector<T> Vec(const int n) {
  vector<T> v(n);
  for (T &x : v) {
    cin >> x;
  }
  return v;
}
template<typename T>
vector<vector<T>> VecVec(const int n, const int m) {
  vector<vector<T>> v(n);
  for (vector<T> &vec : v) {
    vec = Vec<T>(m);
  }
  return v;
}
}// namespace Read

constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;
constexpr int kMaxN = 2e5 + 10;

struct repeat {
  int64 batch = 0;
  int64 count = 0;
};

vector<repeat> simulate(const vector<int> &fof, const vector<int> &keys) {
  bool ceil = false;
  vector<repeat> left;
  vector<repeat> right;
  for (const int b : keys) {
    const int c = fof[b];
    left.push_back({b, (c + ceil) / 2});
    right.push_back({b, (c + !ceil) / 2});
    ceil = ((c & 1) ? !ceil : ceil);
  }

  while (not right.empty()) {
    left.push_back(right.back());
    right.pop_back();
  }

  return left;
}

int64 formula(const int64 b, const int64 x, const int64 l, const int64 r) {
  const int64 part1 = l * r * x;
  const int64 part2 = b * l * x * x;
  const int64 part3 = (r - l + b * x) * b * x * (x - 1) / 2;
  const int64 part4 = b * b * x * (x - 1) * (2 * x - 1) / 6;
  return part1 + part2 + part3 - part4;
}

int64 diversities(const vector<int> &fof, const vector<int> &keys) {
  vector<repeat> repeats = simulate(fof, keys);

  const int kReps = repeats.size();
  vector<int64> pref(kReps);
  vector<int64> suff(kReps);
  for (int i = 1; i < kReps; i++) {
    pref[i] = pref[i - 1] + (repeats[i - 1].batch * repeats[i - 1].count);
  }
  for (int i = kReps - 2; i >= 0; i--) {
    suff[i] = suff[i + 1] + (repeats[i + 1].batch * repeats[i + 1].count);
  }

  const int64 n = suff[0] + repeats[0].batch * repeats[0].count;
  int64 ans = n * (n + 1) / 2;
  for (int i = 0; i < kReps; i++) {
    ans += formula(repeats[i].batch, repeats[i].count, pref[i], suff[i]);
  }

  return ans;
}

class mo_s {
  struct query {
    int l, r, v, t;
    int64 ans;

    query(const int l, const int r, const int v, const int t) : l(l), r(r), v(v), t(t), ans(0) {}
  };

  const int kBlockSize = 550;

  const int n;
  const vector<int> a;
  vector<query> queries;

  [[nodiscard]] int block_of(const int i) const {
    return i / kBlockSize;
  }

public:
  explicit mo_s(const vector<int> &a) : n(a.size()), a(a) {}

  void add_query(const int l, const int r, const int v, const int t) {
    queries.emplace_back(l, r, v, t);
  }

  vector<int64> solve() {
    sort(queries.begin(), queries.end(), [&](const query &q1, const query &q2) {
      if (block_of(q1.l) != block_of(q2.l)) {
        return (q1.l < q2.l);
      }
      return (block_of(q1.l) & 1 ? q1.r < q2.r : q1.r > q2.r);
    });

    const int kDistinct = *max_element(a.begin(), a.end()) + 1;

    const int kMaxFreq = 3e5;
    vector<int> freq(kDistinct);
    vector<int> fof(kMaxFreq + 1); //frequency of frequencies
    vector<int> options;

    fof[0] = kDistinct;

    auto add = [&](const int i) {
      assert(0 <= a[i] and a[i] < kDistinct);
      const int f = freq[a[i]];
      freq[a[i]]++;
      assert (0 <= f and f < kMaxFreq);
      fof[f]--;
      fof[f + 1]++;
      options.push_back(f + 1);
    };

    auto rem = [&](const int i) {
      assert(0 <= a[i] and a[i] < kDistinct);
      const int f = freq[a[i]];
      freq[a[i]]--;
      assert (0 < f and f <= kMaxFreq);
      fof[f]--;
      fof[f - 1]++;
      options.push_back(f - 1);
    };

    for (int i = 0, l = 0, r = -1; i < queries.size(); i++) {
      while (l > queries[i].l) add(--l);
      while (r < queries[i].r) add(++r);
      while (l < queries[i].l) rem(l++);
      while (r > queries[i].r) rem(r--);

      options.erase(remove_if(options.begin(), options.end(), [&](const int x) {
                      return fof[x] == 0;
                    }), options.end());
      sort(options.begin(), options.end());
      options.erase(unique(options.begin(), options.end()), options.end());
      sort(options.begin(), options.end());
      queries[i].ans = diversities(fof, options);
    }

    sort(queries.begin(), queries.end(), [](const query &q1, const query &q2) {
      return q1.t < q2.t;
    });

    vector<int64> ans(queries.size());
    for (int i = 0; const query &q : queries) {
      ans[i++] = q.ans;
    }
    return ans;
  }
};

template<typename T>
class CoordinateCompression {
  bool sorted = false;
  vector<T> v;

public:
  void add(const T &x) {
    v.push_back(x);
  }

  void compress() {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    sorted = true;
  }

  int get(const int x) {
    if (not sorted) assert(false);
    return distance(v.begin(), lower_bound(v.begin(), v.end(), x));
  }

  int size() {
    return v.size();
  }
};

vector<int> compress(vector<int> a) {
  CoordinateCompression<int> cc;
  for (const int x : a) {
    cc.add(x);
  }
  cc.compress();
  for (int &x : a) {
    x = cc.get(x);
  }
  return a;
}

inline void solution() {
  const int n = Read::Int();
  const int q = Read::Int();
  const vector<int> a = compress(Read::Vec<int>(n));

  mo_s mo(a);
  for (int i = 0; i < q; i++) {
    const int l = Read::Int() - 1;
    const int r = Read::Int() - 1;
    mo.add_query(l, r, 0, i);
  }

  vector<int64> ans = mo.solve();
  for (const int64 x : ans) {
    cout << x << '\n';
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  //freopen(".in", "r", stdin);
  //freopen(".out", "w", stdout);

  cout << fixed << setprecision(10);

  int testcases = 1;
  //cin >> testcases;
  while (testcases--) {
    solution();
  }
}

Compilation message

diversity.cpp: In member function 'std::vector<long long int> mo_s::solve()':
diversity.cpp:193:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<mo_s::query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |     for (int i = 0, l = 0, r = -1; i < queries.size(); i++) {
      |                                    ~~^~~~~~~~~~~~~~~~
diversity.cpp:213:21: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
  213 |     for (int i = 0; const query &q : queries) {
      |                     ^~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 2 ms 2648 KB Output is correct
3 Correct 2 ms 3084 KB Output is correct
4 Correct 10 ms 6088 KB Output is correct
5 Correct 19 ms 9400 KB Output is correct
6 Correct 35 ms 13964 KB Output is correct
7 Correct 27 ms 13728 KB Output is correct
8 Correct 30 ms 15224 KB Output is correct
9 Correct 36 ms 14460 KB Output is correct
10 Correct 30 ms 13948 KB Output is correct
11 Correct 30 ms 14668 KB Output is correct
12 Correct 31 ms 13980 KB Output is correct
13 Correct 30 ms 14660 KB Output is correct
14 Correct 30 ms 13976 KB Output is correct
15 Correct 30 ms 14608 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 2 ms 2648 KB Output is correct
3 Correct 2 ms 3084 KB Output is correct
4 Correct 10 ms 6088 KB Output is correct
5 Correct 19 ms 9400 KB Output is correct
6 Correct 35 ms 13964 KB Output is correct
7 Correct 27 ms 13728 KB Output is correct
8 Correct 30 ms 15224 KB Output is correct
9 Correct 36 ms 14460 KB Output is correct
10 Correct 30 ms 13948 KB Output is correct
11 Correct 30 ms 14668 KB Output is correct
12 Correct 31 ms 13980 KB Output is correct
13 Correct 30 ms 14660 KB Output is correct
14 Correct 30 ms 13976 KB Output is correct
15 Correct 30 ms 14608 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 2 ms 2652 KB Output is correct
18 Correct 2 ms 3084 KB Output is correct
19 Correct 12 ms 6088 KB Output is correct
20 Correct 22 ms 10112 KB Output is correct
21 Correct 36 ms 14764 KB Output is correct
22 Correct 39 ms 14720 KB Output is correct
23 Correct 38 ms 15000 KB Output is correct
24 Correct 34 ms 14464 KB Output is correct
25 Correct 34 ms 14964 KB Output is correct
26 Correct 34 ms 14480 KB Output is correct
27 Correct 33 ms 14024 KB Output is correct
28 Correct 32 ms 15404 KB Output is correct
29 Correct 33 ms 15524 KB Output is correct
30 Correct 34 ms 15824 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 2 ms 2648 KB Output is correct
3 Correct 2 ms 3084 KB Output is correct
4 Correct 10 ms 6088 KB Output is correct
5 Correct 19 ms 9400 KB Output is correct
6 Correct 35 ms 13964 KB Output is correct
7 Correct 27 ms 13728 KB Output is correct
8 Correct 30 ms 15224 KB Output is correct
9 Correct 36 ms 14460 KB Output is correct
10 Correct 30 ms 13948 KB Output is correct
11 Correct 30 ms 14668 KB Output is correct
12 Correct 31 ms 13980 KB Output is correct
13 Correct 30 ms 14660 KB Output is correct
14 Correct 30 ms 13976 KB Output is correct
15 Correct 30 ms 14608 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 2 ms 2652 KB Output is correct
18 Correct 2 ms 3084 KB Output is correct
19 Correct 12 ms 6088 KB Output is correct
20 Correct 22 ms 10112 KB Output is correct
21 Correct 36 ms 14764 KB Output is correct
22 Correct 39 ms 14720 KB Output is correct
23 Correct 38 ms 15000 KB Output is correct
24 Correct 34 ms 14464 KB Output is correct
25 Correct 34 ms 14964 KB Output is correct
26 Correct 34 ms 14480 KB Output is correct
27 Correct 33 ms 14024 KB Output is correct
28 Correct 32 ms 15404 KB Output is correct
29 Correct 33 ms 15524 KB Output is correct
30 Correct 34 ms 15824 KB Output is correct
31 Correct 1 ms 2652 KB Output is correct
32 Correct 1 ms 2652 KB Output is correct
33 Correct 1 ms 2652 KB Output is correct
34 Correct 3 ms 3084 KB Output is correct
35 Correct 3 ms 3084 KB Output is correct
36 Correct 3 ms 3084 KB Output is correct
37 Correct 11 ms 4432 KB Output is correct
38 Correct 11 ms 4436 KB Output is correct
39 Correct 21 ms 6000 KB Output is correct
40 Correct 42 ms 9340 KB Output is correct
41 Correct 58 ms 15704 KB Output is correct
42 Correct 60 ms 15092 KB Output is correct
43 Correct 59 ms 14596 KB Output is correct
44 Correct 60 ms 14032 KB Output is correct
45 Correct 62 ms 14456 KB Output is correct
46 Correct 60 ms 13884 KB Output is correct
47 Correct 58 ms 14492 KB Output is correct
48 Correct 58 ms 15496 KB Output is correct
49 Correct 60 ms 14204 KB Output is correct
50 Correct 63 ms 13884 KB Output is correct
51 Correct 62 ms 14212 KB Output is correct
52 Correct 59 ms 14816 KB Output is correct
53 Correct 59 ms 15204 KB Output is correct
54 Correct 58 ms 13720 KB Output is correct
55 Correct 60 ms 14800 KB Output is correct
56 Correct 62 ms 14132 KB Output is correct
57 Correct 59 ms 14400 KB Output is correct
58 Correct 59 ms 13980 KB Output is correct
59 Correct 60 ms 13964 KB Output is correct
60 Correct 59 ms 15480 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 2 ms 2648 KB Output is correct
13 Correct 2 ms 3084 KB Output is correct
14 Correct 10 ms 6088 KB Output is correct
15 Correct 19 ms 9400 KB Output is correct
16 Correct 35 ms 13964 KB Output is correct
17 Correct 27 ms 13728 KB Output is correct
18 Correct 30 ms 15224 KB Output is correct
19 Correct 36 ms 14460 KB Output is correct
20 Correct 30 ms 13948 KB Output is correct
21 Correct 30 ms 14668 KB Output is correct
22 Correct 31 ms 13980 KB Output is correct
23 Correct 30 ms 14660 KB Output is correct
24 Correct 30 ms 13976 KB Output is correct
25 Correct 30 ms 14608 KB Output is correct
26 Correct 1 ms 2652 KB Output is correct
27 Correct 2 ms 2652 KB Output is correct
28 Correct 2 ms 3084 KB Output is correct
29 Correct 12 ms 6088 KB Output is correct
30 Correct 22 ms 10112 KB Output is correct
31 Correct 36 ms 14764 KB Output is correct
32 Correct 39 ms 14720 KB Output is correct
33 Correct 38 ms 15000 KB Output is correct
34 Correct 34 ms 14464 KB Output is correct
35 Correct 34 ms 14964 KB Output is correct
36 Correct 34 ms 14480 KB Output is correct
37 Correct 33 ms 14024 KB Output is correct
38 Correct 32 ms 15404 KB Output is correct
39 Correct 33 ms 15524 KB Output is correct
40 Correct 34 ms 15824 KB Output is correct
41 Correct 1 ms 2652 KB Output is correct
42 Correct 1 ms 2652 KB Output is correct
43 Correct 1 ms 2652 KB Output is correct
44 Correct 3 ms 3084 KB Output is correct
45 Correct 3 ms 3084 KB Output is correct
46 Correct 3 ms 3084 KB Output is correct
47 Correct 11 ms 4432 KB Output is correct
48 Correct 11 ms 4436 KB Output is correct
49 Correct 21 ms 6000 KB Output is correct
50 Correct 42 ms 9340 KB Output is correct
51 Correct 58 ms 15704 KB Output is correct
52 Correct 60 ms 15092 KB Output is correct
53 Correct 59 ms 14596 KB Output is correct
54 Correct 60 ms 14032 KB Output is correct
55 Correct 62 ms 14456 KB Output is correct
56 Correct 60 ms 13884 KB Output is correct
57 Correct 58 ms 14492 KB Output is correct
58 Correct 58 ms 15496 KB Output is correct
59 Correct 60 ms 14204 KB Output is correct
60 Correct 63 ms 13884 KB Output is correct
61 Correct 62 ms 14212 KB Output is correct
62 Correct 59 ms 14816 KB Output is correct
63 Correct 59 ms 15204 KB Output is correct
64 Correct 58 ms 13720 KB Output is correct
65 Correct 60 ms 14800 KB Output is correct
66 Correct 62 ms 14132 KB Output is correct
67 Correct 59 ms 14400 KB Output is correct
68 Correct 59 ms 13980 KB Output is correct
69 Correct 60 ms 13964 KB Output is correct
70 Correct 59 ms 15480 KB Output is correct
71 Correct 12 ms 4436 KB Output is correct
72 Correct 12 ms 4432 KB Output is correct
73 Correct 11 ms 4436 KB Output is correct
74 Correct 11 ms 4436 KB Output is correct
75 Correct 12 ms 4688 KB Output is correct
76 Correct 23 ms 6084 KB Output is correct
77 Correct 23 ms 6088 KB Output is correct
78 Correct 23 ms 5996 KB Output is correct
79 Correct 24 ms 5996 KB Output is correct
80 Correct 24 ms 6088 KB Output is correct
81 Correct 52 ms 9604 KB Output is correct
82 Correct 47 ms 9584 KB Output is correct
83 Correct 47 ms 9392 KB Output is correct
84 Correct 47 ms 9388 KB Output is correct
85 Correct 48 ms 9604 KB Output is correct
86 Correct 50 ms 9576 KB Output is correct
87 Correct 53 ms 9628 KB Output is correct
88 Correct 50 ms 9648 KB Output is correct
89 Correct 50 ms 9656 KB Output is correct
90 Correct 51 ms 10156 KB Output is correct
91 Correct 91 ms 14968 KB Output is correct
92 Correct 85 ms 15596 KB Output is correct
93 Correct 85 ms 15536 KB Output is correct
94 Correct 83 ms 15772 KB Output is correct
95 Correct 85 ms 15956 KB Output is correct
96 Correct 100 ms 16764 KB Output is correct
97 Correct 102 ms 15480 KB Output is correct
98 Correct 89 ms 16652 KB Output is correct
99 Correct 99 ms 16180 KB Output is correct
100 Correct 99 ms 15992 KB Output is correct
101 Correct 92 ms 16792 KB Output is correct
102 Correct 90 ms 16024 KB Output is correct
103 Correct 89 ms 15516 KB Output is correct
104 Correct 97 ms 15988 KB Output is correct
105 Correct 95 ms 16244 KB Output is correct
106 Correct 96 ms 17280 KB Output is correct
107 Correct 89 ms 16504 KB Output is correct
108 Correct 89 ms 16624 KB Output is correct
109 Correct 92 ms 16008 KB Output is correct
110 Correct 92 ms 15888 KB Output is correct
111 Correct 98 ms 15736 KB Output is correct
112 Correct 91 ms 17016 KB Output is correct
113 Correct 94 ms 17532 KB Output is correct
114 Correct 101 ms 15996 KB Output is correct
115 Correct 91 ms 16284 KB Output is correct

Subtask #6
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 2 ms 2648 KB Output is correct
13 Correct 2 ms 3084 KB Output is correct
14 Correct 10 ms 6088 KB Output is correct
15 Correct 19 ms 9400 KB Output is correct
16 Correct 35 ms 13964 KB Output is correct
17 Correct 27 ms 13728 KB Output is correct
18 Correct 30 ms 15224 KB Output is correct
19 Correct 36 ms 14460 KB Output is correct
20 Correct 30 ms 13948 KB Output is correct
21 Correct 30 ms 14668 KB Output is correct
22 Correct 31 ms 13980 KB Output is correct
23 Correct 30 ms 14660 KB Output is correct
24 Correct 30 ms 13976 KB Output is correct
25 Correct 30 ms 14608 KB Output is correct
26 Correct 1 ms 2652 KB Output is correct
27 Correct 2 ms 2652 KB Output is correct
28 Correct 2 ms 3084 KB Output is correct
29 Correct 12 ms 6088 KB Output is correct
30 Correct 22 ms 10112 KB Output is correct
31 Correct 36 ms 14764 KB Output is correct
32 Correct 39 ms 14720 KB Output is correct
33 Correct 38 ms 15000 KB Output is correct
34 Correct 34 ms 14464 KB Output is correct
35 Correct 34 ms 14964 KB Output is correct
36 Correct 34 ms 14480 KB Output is correct
37 Correct 33 ms 14024 KB Output is correct
38 Correct 32 ms 15404 KB Output is correct
39 Correct 33 ms 15524 KB Output is correct
40 Correct 34 ms 15824 KB Output is correct
41 Correct 1 ms 2652 KB Output is correct
42 Correct 1 ms 2652 KB Output is correct
43 Correct 1 ms 2652 KB Output is correct
44 Correct 3 ms 3084 KB Output is correct
45 Correct 3 ms 3084 KB Output is correct
46 Correct 3 ms 3084 KB Output is correct
47 Correct 11 ms 4432 KB Output is correct
48 Correct 11 ms 4436 KB Output is correct
49 Correct 21 ms 6000 KB Output is correct
50 Correct 42 ms 9340 KB Output is correct
51 Correct 58 ms 15704 KB Output is correct
52 Correct 60 ms 15092 KB Output is correct
53 Correct 59 ms 14596 KB Output is correct
54 Correct 60 ms 14032 KB Output is correct
55 Correct 62 ms 14456 KB Output is correct
56 Correct 60 ms 13884 KB Output is correct
57 Correct 58 ms 14492 KB Output is correct
58 Correct 58 ms 15496 KB Output is correct
59 Correct 60 ms 14204 KB Output is correct
60 Correct 63 ms 13884 KB Output is correct
61 Correct 62 ms 14212 KB Output is correct
62 Correct 59 ms 14816 KB Output is correct
63 Correct 59 ms 15204 KB Output is correct
64 Correct 58 ms 13720 KB Output is correct
65 Correct 60 ms 14800 KB Output is correct
66 Correct 62 ms 14132 KB Output is correct
67 Correct 59 ms 14400 KB Output is correct
68 Correct 59 ms 13980 KB Output is correct
69 Correct 60 ms 13964 KB Output is correct
70 Correct 59 ms 15480 KB Output is correct
71 Correct 12 ms 4436 KB Output is correct
72 Correct 12 ms 4432 KB Output is correct
73 Correct 11 ms 4436 KB Output is correct
74 Correct 11 ms 4436 KB Output is correct
75 Correct 12 ms 4688 KB Output is correct
76 Correct 23 ms 6084 KB Output is correct
77 Correct 23 ms 6088 KB Output is correct
78 Correct 23 ms 5996 KB Output is correct
79 Correct 24 ms 5996 KB Output is correct
80 Correct 24 ms 6088 KB Output is correct
81 Correct 52 ms 9604 KB Output is correct
82 Correct 47 ms 9584 KB Output is correct
83 Correct 47 ms 9392 KB Output is correct
84 Correct 47 ms 9388 KB Output is correct
85 Correct 48 ms 9604 KB Output is correct
86 Correct 50 ms 9576 KB Output is correct
87 Correct 53 ms 9628 KB Output is correct
88 Correct 50 ms 9648 KB Output is correct
89 Correct 50 ms 9656 KB Output is correct
90 Correct 51 ms 10156 KB Output is correct
91 Correct 91 ms 14968 KB Output is correct
92 Correct 85 ms 15596 KB Output is correct
93 Correct 85 ms 15536 KB Output is correct
94 Correct 83 ms 15772 KB Output is correct
95 Correct 85 ms 15956 KB Output is correct
96 Correct 100 ms 16764 KB Output is correct
97 Correct 102 ms 15480 KB Output is correct
98 Correct 89 ms 16652 KB Output is correct
99 Correct 99 ms 16180 KB Output is correct
100 Correct 99 ms 15992 KB Output is correct
101 Correct 92 ms 16792 KB Output is correct
102 Correct 90 ms 16024 KB Output is correct
103 Correct 89 ms 15516 KB Output is correct
104 Correct 97 ms 15988 KB Output is correct
105 Correct 95 ms 16244 KB Output is correct
106 Correct 96 ms 17280 KB Output is correct
107 Correct 89 ms 16504 KB Output is correct
108 Correct 89 ms 16624 KB Output is correct
109 Correct 92 ms 16008 KB Output is correct
110 Correct 92 ms 15888 KB Output is correct
111 Correct 98 ms 15736 KB Output is correct
112 Correct 91 ms 17016 KB Output is correct
113 Correct 94 ms 17532 KB Output is correct
114 Correct 101 ms 15996 KB Output is correct
115 Correct 91 ms 16284 KB Output is correct
116 Correct 278 ms 5392 KB Output is correct
117 Correct 417 ms 6016 KB Output is correct
118 Correct 497 ms 6448 KB Output is correct
119 Correct 774 ms 6456 KB Output is correct
120 Correct 673 ms 6472 KB Output is correct
121 Correct 1159 ms 8348 KB Output is correct
122 Correct 1002 ms 8708 KB Output is correct
123 Correct 2481 ms 12028 KB Output is correct
124 Correct 1882 ms 12284 KB Output is correct
125 Correct 1621 ms 12148 KB Output is correct
126 Correct 2426 ms 18548 KB Output is correct
127 Correct 2499 ms 20260 KB Output is correct
128 Correct 2447 ms 19488 KB Output is correct
129 Correct 2481 ms 19188 KB Output is correct
130 Correct 2494 ms 19036 KB Output is correct
131 Correct 3432 ms 18676 KB Output is correct
132 Correct 3433 ms 19764 KB Output is correct
133 Correct 3258 ms 18540 KB Output is correct
134 Correct 3392 ms 20116 KB Output is correct
135 Correct 3368 ms 20416 KB Output is correct
136 Correct 3458 ms 18392 KB Output is correct
137 Correct 3359 ms 19212 KB Output is correct
138 Correct 3474 ms 18900 KB Output is correct
139 Correct 3379 ms 19292 KB Output is correct
140 Correct 3416 ms 18920 KB Output is correct
141 Correct 4136 ms 18688 KB Output is correct
142 Correct 4178 ms 19444 KB Output is correct
143 Correct 4127 ms 19280 KB Output is correct
144 Correct 4157 ms 18480 KB Output is correct
145 Correct 4144 ms 18788 KB Output is correct
146 Correct 3627 ms 19148 KB Output is correct
147 Correct 3633 ms 19680 KB Output is correct
148 Correct 3670 ms 19104 KB Output is correct
149 Correct 3670 ms 19628 KB Output is correct
150 Correct 3665 ms 20336 KB Output is correct
151 Correct 3227 ms 20140 KB Output is correct
152 Correct 3209 ms 18840 KB Output is correct
153 Correct 3235 ms 21092 KB Output is correct
154 Correct 3226 ms 19708 KB Output is correct
155 Correct 3224 ms 18624 KB Output is correct
156 Correct 3113 ms 21248 KB Output is correct
157 Correct 3125 ms 19848 KB Output is correct
158 Correct 3142 ms 19952 KB Output is correct
159 Correct 3151 ms 19296 KB Output is correct
160 Correct 3167 ms 20112 KB Output is correct
161 Correct 2060 ms 21256 KB Output is correct
162 Correct 2069 ms 21196 KB Output is correct
163 Correct 2043 ms 21180 KB Output is correct
164 Correct 2066 ms 20760 KB Output is correct
165 Correct 2053 ms 21160 KB Output is correct
166 Correct 3022 ms 20096 KB Output is correct
167 Correct 3074 ms 19552 KB Output is correct
168 Correct 3063 ms 20952 KB Output is correct
169 Correct 2999 ms 19632 KB Output is correct
170 Correct 3010 ms 21096 KB Output is correct
171 Correct 2293 ms 20168 KB Output is correct
172 Correct 2321 ms 19852 KB Output is correct
173 Correct 2299 ms 19436 KB Output is correct
174 Correct 2268 ms 19632 KB Output is correct
175 Correct 2331 ms 18992 KB Output is correct