oj.uz

Submission #868003

# Submission time Handle Problem Language Result Execution time Memory
868003 2023-10-30T07:32:04 Z evenvalue Diversity (CEOI21_diversity) C++17
100 / 100
 3997 ms 21232 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) {
      const int f = freq[a[i]]++;
      fof[f]--;
      fof[f + 1]++;
      options.push_back(f + 1);
    };
 
    auto rem = [&](const int i) {
      const int f = freq[a[i]]--;
      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());
      
      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:187: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]
  187 |     for (int i = 0, l = 0, r = -1; i < queries.size(); i++) {
      |                                    ~~^~~~~~~~~~~~~~~~
diversity.cpp:207:21: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
  207 |     for (int i = 0; const query &q : queries) {
      |                     ^~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 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 2708 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2780 KB Output is correct
8 Correct 1 ms 2760 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2648 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 1 ms 2652 KB Output is correct
3 Correct 2 ms 3084 KB Output is correct
4 Correct 10 ms 6344 KB Output is correct
5 Correct 19 ms 9912 KB Output is correct
6 Correct 31 ms 15488 KB Output is correct
7 Correct 29 ms 15796 KB Output is correct
8 Correct 36 ms 15008 KB Output is correct
9 Correct 29 ms 14372 KB Output is correct
10 Correct 30 ms 15444 KB Output is correct
11 Correct 29 ms 16164 KB Output is correct
12 Correct 30 ms 14544 KB Output is correct
13 Correct 30 ms 16304 KB Output is correct
14 Correct 30 ms 15784 KB Output is correct
15 Correct 30 ms 15732 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 1 ms 2652 KB Output is correct
3 Correct 2 ms 3084 KB Output is correct
4 Correct 10 ms 6344 KB Output is correct
5 Correct 19 ms 9912 KB Output is correct
6 Correct 31 ms 15488 KB Output is correct
7 Correct 29 ms 15796 KB Output is correct
8 Correct 36 ms 15008 KB Output is correct
9 Correct 29 ms 14372 KB Output is correct
10 Correct 30 ms 15444 KB Output is correct
11 Correct 29 ms 16164 KB Output is correct
12 Correct 30 ms 14544 KB Output is correct
13 Correct 30 ms 16304 KB Output is correct
14 Correct 30 ms 15784 KB Output is correct
15 Correct 30 ms 15732 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 2 ms 3084 KB Output is correct
19 Correct 11 ms 6268 KB Output is correct
20 Correct 22 ms 10416 KB Output is correct
21 Correct 32 ms 15132 KB Output is correct
22 Correct 33 ms 16088 KB Output is correct
23 Correct 34 ms 15612 KB Output is correct
24 Correct 34 ms 15464 KB Output is correct
25 Correct 34 ms 15004 KB Output is correct
26 Correct 36 ms 15132 KB Output is correct
27 Correct 33 ms 15492 KB Output is correct
28 Correct 33 ms 16236 KB Output is correct
29 Correct 33 ms 14604 KB Output is correct
30 Correct 34 ms 14844 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 1 ms 2652 KB Output is correct
3 Correct 2 ms 3084 KB Output is correct
4 Correct 10 ms 6344 KB Output is correct
5 Correct 19 ms 9912 KB Output is correct
6 Correct 31 ms 15488 KB Output is correct
7 Correct 29 ms 15796 KB Output is correct
8 Correct 36 ms 15008 KB Output is correct
9 Correct 29 ms 14372 KB Output is correct
10 Correct 30 ms 15444 KB Output is correct
11 Correct 29 ms 16164 KB Output is correct
12 Correct 30 ms 14544 KB Output is correct
13 Correct 30 ms 16304 KB Output is correct
14 Correct 30 ms 15784 KB Output is correct
15 Correct 30 ms 15732 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 2 ms 3084 KB Output is correct
19 Correct 11 ms 6268 KB Output is correct
20 Correct 22 ms 10416 KB Output is correct
21 Correct 32 ms 15132 KB Output is correct
22 Correct 33 ms 16088 KB Output is correct
23 Correct 34 ms 15612 KB Output is correct
24 Correct 34 ms 15464 KB Output is correct
25 Correct 34 ms 15004 KB Output is correct
26 Correct 36 ms 15132 KB Output is correct
27 Correct 33 ms 15492 KB Output is correct
28 Correct 33 ms 16236 KB Output is correct
29 Correct 33 ms 14604 KB Output is correct
30 Correct 34 ms 14844 KB Output is correct
31 Correct 1 ms 2652 KB Output is correct
32 Correct 1 ms 2720 KB Output is correct
33 Correct 1 ms 2724 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 13 ms 4692 KB Output is correct
38 Correct 11 ms 4692 KB Output is correct
39 Correct 20 ms 6332 KB Output is correct
40 Correct 39 ms 10228 KB Output is correct
41 Correct 59 ms 15096 KB Output is correct
42 Correct 59 ms 15900 KB Output is correct
43 Correct 59 ms 15828 KB Output is correct
44 Correct 65 ms 15608 KB Output is correct
45 Correct 59 ms 15972 KB Output is correct
46 Correct 58 ms 16460 KB Output is correct
47 Correct 58 ms 16640 KB Output is correct
48 Correct 58 ms 15524 KB Output is correct
49 Correct 58 ms 15260 KB Output is correct
50 Correct 58 ms 15004 KB Output is correct
51 Correct 59 ms 14992 KB Output is correct
52 Correct 60 ms 15336 KB Output is correct
53 Correct 58 ms 15632 KB Output is correct
54 Correct 59 ms 15804 KB Output is correct
55 Correct 58 ms 15088 KB Output is correct
56 Correct 59 ms 16284 KB Output is correct
57 Correct 66 ms 16928 KB Output is correct
58 Correct 58 ms 15112 KB Output is correct
59 Correct 60 ms 16648 KB Output is correct
60 Correct 64 ms 16828 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 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 2708 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2780 KB Output is correct
8 Correct 1 ms 2760 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 2 ms 3084 KB Output is correct
14 Correct 10 ms 6344 KB Output is correct
15 Correct 19 ms 9912 KB Output is correct
16 Correct 31 ms 15488 KB Output is correct
17 Correct 29 ms 15796 KB Output is correct
18 Correct 36 ms 15008 KB Output is correct
19 Correct 29 ms 14372 KB Output is correct
20 Correct 30 ms 15444 KB Output is correct
21 Correct 29 ms 16164 KB Output is correct
22 Correct 30 ms 14544 KB Output is correct
23 Correct 30 ms 16304 KB Output is correct
24 Correct 30 ms 15784 KB Output is correct
25 Correct 30 ms 15732 KB Output is correct
26 Correct 1 ms 2652 KB Output is correct
27 Correct 1 ms 2652 KB Output is correct
28 Correct 2 ms 3084 KB Output is correct
29 Correct 11 ms 6268 KB Output is correct
30 Correct 22 ms 10416 KB Output is correct
31 Correct 32 ms 15132 KB Output is correct
32 Correct 33 ms 16088 KB Output is correct
33 Correct 34 ms 15612 KB Output is correct
34 Correct 34 ms 15464 KB Output is correct
35 Correct 34 ms 15004 KB Output is correct
36 Correct 36 ms 15132 KB Output is correct
37 Correct 33 ms 15492 KB Output is correct
38 Correct 33 ms 16236 KB Output is correct
39 Correct 33 ms 14604 KB Output is correct
40 Correct 34 ms 14844 KB Output is correct
41 Correct 1 ms 2652 KB Output is correct
42 Correct 1 ms 2720 KB Output is correct
43 Correct 1 ms 2724 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 13 ms 4692 KB Output is correct
48 Correct 11 ms 4692 KB Output is correct
49 Correct 20 ms 6332 KB Output is correct
50 Correct 39 ms 10228 KB Output is correct
51 Correct 59 ms 15096 KB Output is correct
52 Correct 59 ms 15900 KB Output is correct
53 Correct 59 ms 15828 KB Output is correct
54 Correct 65 ms 15608 KB Output is correct
55 Correct 59 ms 15972 KB Output is correct
56 Correct 58 ms 16460 KB Output is correct
57 Correct 58 ms 16640 KB Output is correct
58 Correct 58 ms 15524 KB Output is correct
59 Correct 58 ms 15260 KB Output is correct
60 Correct 58 ms 15004 KB Output is correct
61 Correct 59 ms 14992 KB Output is correct
62 Correct 60 ms 15336 KB Output is correct
63 Correct 58 ms 15632 KB Output is correct
64 Correct 59 ms 15804 KB Output is correct
65 Correct 58 ms 15088 KB Output is correct
66 Correct 59 ms 16284 KB Output is correct
67 Correct 66 ms 16928 KB Output is correct
68 Correct 58 ms 15112 KB Output is correct
69 Correct 60 ms 16648 KB Output is correct
70 Correct 64 ms 16828 KB Output is correct
71 Correct 11 ms 4688 KB Output is correct
72 Correct 11 ms 4688 KB Output is correct
73 Correct 12 ms 4692 KB Output is correct
74 Correct 11 ms 4744 KB Output is correct
75 Correct 12 ms 4692 KB Output is correct
76 Correct 23 ms 6596 KB Output is correct
77 Correct 23 ms 6456 KB Output is correct
78 Correct 23 ms 6456 KB Output is correct
79 Correct 23 ms 6596 KB Output is correct
80 Correct 26 ms 7104 KB Output is correct
81 Correct 47 ms 10532 KB Output is correct
82 Correct 47 ms 10416 KB Output is correct
83 Correct 52 ms 10552 KB Output is correct
84 Correct 48 ms 10412 KB Output is correct
85 Correct 48 ms 10548 KB Output is correct
86 Correct 54 ms 10644 KB Output is correct
87 Correct 50 ms 10660 KB Output is correct
88 Correct 50 ms 10660 KB Output is correct
89 Correct 50 ms 10672 KB Output is correct
90 Correct 50 ms 10672 KB Output is correct
91 Correct 86 ms 17464 KB Output is correct
92 Correct 83 ms 16704 KB Output is correct
93 Correct 83 ms 17972 KB Output is correct
94 Correct 85 ms 17716 KB Output is correct
95 Correct 82 ms 18224 KB Output is correct
96 Correct 92 ms 18388 KB Output is correct
97 Correct 90 ms 17372 KB Output is correct
98 Correct 91 ms 18640 KB Output is correct
99 Correct 88 ms 18300 KB Output is correct
100 Correct 90 ms 17628 KB Output is correct
101 Correct 89 ms 17712 KB Output is correct
102 Correct 90 ms 17884 KB Output is correct
103 Correct 90 ms 17884 KB Output is correct
104 Correct 92 ms 17532 KB Output is correct
105 Correct 88 ms 17508 KB Output is correct
106 Correct 90 ms 17660 KB Output is correct
107 Correct 87 ms 19500 KB Output is correct
108 Correct 88 ms 18940 KB Output is correct
109 Correct 92 ms 18372 KB Output is correct
110 Correct 92 ms 17684 KB Output is correct
111 Correct 89 ms 17656 KB Output is correct
112 Correct 88 ms 18060 KB Output is correct
113 Correct 90 ms 18948 KB Output is correct
114 Correct 93 ms 18048 KB Output is correct
115 Correct 90 ms 18952 KB Output is correct

Subtask #6
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 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 2708 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2780 KB Output is correct
8 Correct 1 ms 2760 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 2 ms 3084 KB Output is correct
14 Correct 10 ms 6344 KB Output is correct
15 Correct 19 ms 9912 KB Output is correct
16 Correct 31 ms 15488 KB Output is correct
17 Correct 29 ms 15796 KB Output is correct
18 Correct 36 ms 15008 KB Output is correct
19 Correct 29 ms 14372 KB Output is correct
20 Correct 30 ms 15444 KB Output is correct
21 Correct 29 ms 16164 KB Output is correct
22 Correct 30 ms 14544 KB Output is correct
23 Correct 30 ms 16304 KB Output is correct
24 Correct 30 ms 15784 KB Output is correct
25 Correct 30 ms 15732 KB Output is correct
26 Correct 1 ms 2652 KB Output is correct
27 Correct 1 ms 2652 KB Output is correct
28 Correct 2 ms 3084 KB Output is correct
29 Correct 11 ms 6268 KB Output is correct
30 Correct 22 ms 10416 KB Output is correct
31 Correct 32 ms 15132 KB Output is correct
32 Correct 33 ms 16088 KB Output is correct
33 Correct 34 ms 15612 KB Output is correct
34 Correct 34 ms 15464 KB Output is correct
35 Correct 34 ms 15004 KB Output is correct
36 Correct 36 ms 15132 KB Output is correct
37 Correct 33 ms 15492 KB Output is correct
38 Correct 33 ms 16236 KB Output is correct
39 Correct 33 ms 14604 KB Output is correct
40 Correct 34 ms 14844 KB Output is correct
41 Correct 1 ms 2652 KB Output is correct
42 Correct 1 ms 2720 KB Output is correct
43 Correct 1 ms 2724 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 13 ms 4692 KB Output is correct
48 Correct 11 ms 4692 KB Output is correct
49 Correct 20 ms 6332 KB Output is correct
50 Correct 39 ms 10228 KB Output is correct
51 Correct 59 ms 15096 KB Output is correct
52 Correct 59 ms 15900 KB Output is correct
53 Correct 59 ms 15828 KB Output is correct
54 Correct 65 ms 15608 KB Output is correct
55 Correct 59 ms 15972 KB Output is correct
56 Correct 58 ms 16460 KB Output is correct
57 Correct 58 ms 16640 KB Output is correct
58 Correct 58 ms 15524 KB Output is correct
59 Correct 58 ms 15260 KB Output is correct
60 Correct 58 ms 15004 KB Output is correct
61 Correct 59 ms 14992 KB Output is correct
62 Correct 60 ms 15336 KB Output is correct
63 Correct 58 ms 15632 KB Output is correct
64 Correct 59 ms 15804 KB Output is correct
65 Correct 58 ms 15088 KB Output is correct
66 Correct 59 ms 16284 KB Output is correct
67 Correct 66 ms 16928 KB Output is correct
68 Correct 58 ms 15112 KB Output is correct
69 Correct 60 ms 16648 KB Output is correct
70 Correct 64 ms 16828 KB Output is correct
71 Correct 11 ms 4688 KB Output is correct
72 Correct 11 ms 4688 KB Output is correct
73 Correct 12 ms 4692 KB Output is correct
74 Correct 11 ms 4744 KB Output is correct
75 Correct 12 ms 4692 KB Output is correct
76 Correct 23 ms 6596 KB Output is correct
77 Correct 23 ms 6456 KB Output is correct
78 Correct 23 ms 6456 KB Output is correct
79 Correct 23 ms 6596 KB Output is correct
80 Correct 26 ms 7104 KB Output is correct
81 Correct 47 ms 10532 KB Output is correct
82 Correct 47 ms 10416 KB Output is correct
83 Correct 52 ms 10552 KB Output is correct
84 Correct 48 ms 10412 KB Output is correct
85 Correct 48 ms 10548 KB Output is correct
86 Correct 54 ms 10644 KB Output is correct
87 Correct 50 ms 10660 KB Output is correct
88 Correct 50 ms 10660 KB Output is correct
89 Correct 50 ms 10672 KB Output is correct
90 Correct 50 ms 10672 KB Output is correct
91 Correct 86 ms 17464 KB Output is correct
92 Correct 83 ms 16704 KB Output is correct
93 Correct 83 ms 17972 KB Output is correct
94 Correct 85 ms 17716 KB Output is correct
95 Correct 82 ms 18224 KB Output is correct
96 Correct 92 ms 18388 KB Output is correct
97 Correct 90 ms 17372 KB Output is correct
98 Correct 91 ms 18640 KB Output is correct
99 Correct 88 ms 18300 KB Output is correct
100 Correct 90 ms 17628 KB Output is correct
101 Correct 89 ms 17712 KB Output is correct
102 Correct 90 ms 17884 KB Output is correct
103 Correct 90 ms 17884 KB Output is correct
104 Correct 92 ms 17532 KB Output is correct
105 Correct 88 ms 17508 KB Output is correct
106 Correct 90 ms 17660 KB Output is correct
107 Correct 87 ms 19500 KB Output is correct
108 Correct 88 ms 18940 KB Output is correct
109 Correct 92 ms 18372 KB Output is correct
110 Correct 92 ms 17684 KB Output is correct
111 Correct 89 ms 17656 KB Output is correct
112 Correct 88 ms 18060 KB Output is correct
113 Correct 90 ms 18948 KB Output is correct
114 Correct 93 ms 18048 KB Output is correct
115 Correct 90 ms 18952 KB Output is correct
116 Correct 267 ms 6340 KB Output is correct
117 Correct 395 ms 5884 KB Output is correct
118 Correct 454 ms 7108 KB Output is correct
119 Correct 729 ms 7208 KB Output is correct
120 Correct 640 ms 7216 KB Output is correct
121 Correct 1091 ms 9248 KB Output is correct
122 Correct 941 ms 9144 KB Output is correct
123 Correct 2304 ms 13420 KB Output is correct
124 Correct 1825 ms 13592 KB Output is correct
125 Correct 1573 ms 13636 KB Output is correct
126 Correct 2291 ms 19144 KB Output is correct
127 Correct 2327 ms 18760 KB Output is correct
128 Correct 2340 ms 19100 KB Output is correct
129 Correct 2341 ms 18648 KB Output is correct
130 Correct 2383 ms 18712 KB Output is correct
131 Correct 3248 ms 19196 KB Output is correct
132 Correct 3300 ms 18980 KB Output is correct
133 Correct 3087 ms 20648 KB Output is correct
134 Correct 3225 ms 19404 KB Output is correct
135 Correct 3213 ms 18824 KB Output is correct
136 Correct 3326 ms 19628 KB Output is correct
137 Correct 3221 ms 18988 KB Output is correct
138 Correct 3335 ms 18072 KB Output is correct
139 Correct 3224 ms 18228 KB Output is correct
140 Correct 3249 ms 19484 KB Output is correct
141 Correct 3983 ms 19484 KB Output is correct
142 Correct 3966 ms 19872 KB Output is correct
143 Correct 3994 ms 19400 KB Output is correct
144 Correct 3982 ms 18200 KB Output is correct
145 Correct 3997 ms 18540 KB Output is correct
146 Correct 3531 ms 18356 KB Output is correct
147 Correct 3543 ms 18660 KB Output is correct
148 Correct 3569 ms 20060 KB Output is correct
149 Correct 3553 ms 19076 KB Output is correct
150 Correct 3559 ms 19084 KB Output is correct
151 Correct 3133 ms 19144 KB Output is correct
152 Correct 3121 ms 21232 KB Output is correct
153 Correct 3163 ms 20696 KB Output is correct
154 Correct 3130 ms 19344 KB Output is correct
155 Correct 3138 ms 19120 KB Output is correct
156 Correct 3076 ms 19716 KB Output is correct
157 Correct 3020 ms 21108 KB Output is correct
158 Correct 3018 ms 19868 KB Output is correct
159 Correct 3053 ms 20120 KB Output is correct
160 Correct 3044 ms 20392 KB Output is correct
161 Correct 2008 ms 21020 KB Output is correct
162 Correct 1993 ms 19600 KB Output is correct
163 Correct 1973 ms 19448 KB Output is correct
164 Correct 1983 ms 19672 KB Output is correct
165 Correct 1967 ms 20856 KB Output is correct
166 Correct 2916 ms 19280 KB Output is correct
167 Correct 2965 ms 19036 KB Output is correct
168 Correct 2947 ms 20256 KB Output is correct
169 Correct 2900 ms 18764 KB Output is correct
170 Correct 2907 ms 19144 KB Output is correct
171 Correct 2204 ms 20036 KB Output is correct
172 Correct 2226 ms 19012 KB Output is correct
173 Correct 2197 ms 19624 KB Output is correct
174 Correct 2172 ms 20584 KB Output is correct
175 Correct 2266 ms 18988 KB Output is correct