oj.uz

답안 #868101

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
868101 2023-10-30T12:33:10 Z evenvalue Diversity (CEOI21_diversity) C++17
100 / 100
 4102 ms 12532 KB 
#include <bits/stdc++.h>
using namespace std;
 
#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:185:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<mo_s::query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |     for (int i = 0, l = 0, r = -1; i < queries.size(); i++) {
      |                                    ~~^~~~~~~~~~~~~~~~
diversity.cpp:205:21: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
  205 |     for (int i = 0; const query &q : queries) {
      |                     ^~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1476 KB Output is correct
3 Correct 1 ms 1624 KB Output is correct
4 Correct 1 ms 1624 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1 ms 1484 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1636 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 2 ms 1628 KB Output is correct
4 Correct 12 ms 3492 KB Output is correct
5 Correct 18 ms 5320 KB Output is correct
6 Correct 29 ms 7832 KB Output is correct
7 Correct 26 ms 7736 KB Output is correct
8 Correct 30 ms 7780 KB Output is correct
9 Correct 39 ms 7764 KB Output is correct
10 Correct 35 ms 7660 KB Output is correct
11 Correct 27 ms 7736 KB Output is correct
12 Correct 28 ms 7732 KB Output is correct
13 Correct 39 ms 7636 KB Output is correct
14 Correct 29 ms 7784 KB Output is correct
15 Correct 28 ms 7604 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 2 ms 1628 KB Output is correct
4 Correct 12 ms 3492 KB Output is correct
5 Correct 18 ms 5320 KB Output is correct
6 Correct 29 ms 7832 KB Output is correct
7 Correct 26 ms 7736 KB Output is correct
8 Correct 30 ms 7780 KB Output is correct
9 Correct 39 ms 7764 KB Output is correct
10 Correct 35 ms 7660 KB Output is correct
11 Correct 27 ms 7736 KB Output is correct
12 Correct 28 ms 7732 KB Output is correct
13 Correct 39 ms 7636 KB Output is correct
14 Correct 29 ms 7784 KB Output is correct
15 Correct 28 ms 7604 KB Output is correct
16 Correct 1 ms 1628 KB Output is correct
17 Correct 1 ms 1628 KB Output is correct
18 Correct 2 ms 1628 KB Output is correct
19 Correct 11 ms 3408 KB Output is correct
20 Correct 30 ms 5316 KB Output is correct
21 Correct 31 ms 7988 KB Output is correct
22 Correct 41 ms 7920 KB Output is correct
23 Correct 31 ms 7944 KB Output is correct
24 Correct 31 ms 8000 KB Output is correct
25 Correct 32 ms 7920 KB Output is correct
26 Correct 45 ms 7736 KB Output is correct
27 Correct 31 ms 7856 KB Output is correct
28 Correct 30 ms 7724 KB Output is correct
29 Correct 32 ms 7740 KB Output is correct
30 Correct 40 ms 7960 KB Output is correct

Subtask #4
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 2 ms 1628 KB Output is correct
4 Correct 12 ms 3492 KB Output is correct
5 Correct 18 ms 5320 KB Output is correct
6 Correct 29 ms 7832 KB Output is correct
7 Correct 26 ms 7736 KB Output is correct
8 Correct 30 ms 7780 KB Output is correct
9 Correct 39 ms 7764 KB Output is correct
10 Correct 35 ms 7660 KB Output is correct
11 Correct 27 ms 7736 KB Output is correct
12 Correct 28 ms 7732 KB Output is correct
13 Correct 39 ms 7636 KB Output is correct
14 Correct 29 ms 7784 KB Output is correct
15 Correct 28 ms 7604 KB Output is correct
16 Correct 1 ms 1628 KB Output is correct
17 Correct 1 ms 1628 KB Output is correct
18 Correct 2 ms 1628 KB Output is correct
19 Correct 11 ms 3408 KB Output is correct
20 Correct 30 ms 5316 KB Output is correct
21 Correct 31 ms 7988 KB Output is correct
22 Correct 41 ms 7920 KB Output is correct
23 Correct 31 ms 7944 KB Output is correct
24 Correct 31 ms 8000 KB Output is correct
25 Correct 32 ms 7920 KB Output is correct
26 Correct 45 ms 7736 KB Output is correct
27 Correct 31 ms 7856 KB Output is correct
28 Correct 30 ms 7724 KB Output is correct
29 Correct 32 ms 7740 KB Output is correct
30 Correct 40 ms 7960 KB Output is correct
31 Correct 1 ms 1628 KB Output is correct
32 Correct 1 ms 1520 KB Output is correct
33 Correct 1 ms 1628 KB Output is correct
34 Correct 3 ms 1628 KB Output is correct
35 Correct 2 ms 1628 KB Output is correct
36 Correct 3 ms 1624 KB Output is correct
37 Correct 9 ms 2520 KB Output is correct
38 Correct 10 ms 2588 KB Output is correct
39 Correct 19 ms 3556 KB Output is correct
40 Correct 39 ms 5556 KB Output is correct
41 Correct 57 ms 8208 KB Output is correct
42 Correct 56 ms 9016 KB Output is correct
43 Correct 63 ms 8264 KB Output is correct
44 Correct 58 ms 8252 KB Output is correct
45 Correct 58 ms 8292 KB Output is correct
46 Correct 58 ms 8248 KB Output is correct
47 Correct 57 ms 8172 KB Output is correct
48 Correct 56 ms 8272 KB Output is correct
49 Correct 60 ms 8352 KB Output is correct
50 Correct 57 ms 8336 KB Output is correct
51 Correct 70 ms 8288 KB Output is correct
52 Correct 59 ms 8112 KB Output is correct
53 Correct 57 ms 8296 KB Output is correct
54 Correct 57 ms 8296 KB Output is correct
55 Correct 74 ms 8244 KB Output is correct
56 Correct 70 ms 8248 KB Output is correct
57 Correct 75 ms 8244 KB Output is correct
58 Correct 56 ms 8244 KB Output is correct
59 Correct 57 ms 8308 KB Output is correct
60 Correct 57 ms 8116 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1476 KB Output is correct
3 Correct 1 ms 1624 KB Output is correct
4 Correct 1 ms 1624 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1 ms 1484 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1636 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 1 ms 1628 KB Output is correct
13 Correct 2 ms 1628 KB Output is correct
14 Correct 12 ms 3492 KB Output is correct
15 Correct 18 ms 5320 KB Output is correct
16 Correct 29 ms 7832 KB Output is correct
17 Correct 26 ms 7736 KB Output is correct
18 Correct 30 ms 7780 KB Output is correct
19 Correct 39 ms 7764 KB Output is correct
20 Correct 35 ms 7660 KB Output is correct
21 Correct 27 ms 7736 KB Output is correct
22 Correct 28 ms 7732 KB Output is correct
23 Correct 39 ms 7636 KB Output is correct
24 Correct 29 ms 7784 KB Output is correct
25 Correct 28 ms 7604 KB Output is correct
26 Correct 1 ms 1628 KB Output is correct
27 Correct 1 ms 1628 KB Output is correct
28 Correct 2 ms 1628 KB Output is correct
29 Correct 11 ms 3408 KB Output is correct
30 Correct 30 ms 5316 KB Output is correct
31 Correct 31 ms 7988 KB Output is correct
32 Correct 41 ms 7920 KB Output is correct
33 Correct 31 ms 7944 KB Output is correct
34 Correct 31 ms 8000 KB Output is correct
35 Correct 32 ms 7920 KB Output is correct
36 Correct 45 ms 7736 KB Output is correct
37 Correct 31 ms 7856 KB Output is correct
38 Correct 30 ms 7724 KB Output is correct
39 Correct 32 ms 7740 KB Output is correct
40 Correct 40 ms 7960 KB Output is correct
41 Correct 1 ms 1628 KB Output is correct
42 Correct 1 ms 1520 KB Output is correct
43 Correct 1 ms 1628 KB Output is correct
44 Correct 3 ms 1628 KB Output is correct
45 Correct 2 ms 1628 KB Output is correct
46 Correct 3 ms 1624 KB Output is correct
47 Correct 9 ms 2520 KB Output is correct
48 Correct 10 ms 2588 KB Output is correct
49 Correct 19 ms 3556 KB Output is correct
50 Correct 39 ms 5556 KB Output is correct
51 Correct 57 ms 8208 KB Output is correct
52 Correct 56 ms 9016 KB Output is correct
53 Correct 63 ms 8264 KB Output is correct
54 Correct 58 ms 8252 KB Output is correct
55 Correct 58 ms 8292 KB Output is correct
56 Correct 58 ms 8248 KB Output is correct
57 Correct 57 ms 8172 KB Output is correct
58 Correct 56 ms 8272 KB Output is correct
59 Correct 60 ms 8352 KB Output is correct
60 Correct 57 ms 8336 KB Output is correct
61 Correct 70 ms 8288 KB Output is correct
62 Correct 59 ms 8112 KB Output is correct
63 Correct 57 ms 8296 KB Output is correct
64 Correct 57 ms 8296 KB Output is correct
65 Correct 74 ms 8244 KB Output is correct
66 Correct 70 ms 8248 KB Output is correct
67 Correct 75 ms 8244 KB Output is correct
68 Correct 56 ms 8244 KB Output is correct
69 Correct 57 ms 8308 KB Output is correct
70 Correct 57 ms 8116 KB Output is correct
71 Correct 12 ms 2584 KB Output is correct
72 Correct 11 ms 2588 KB Output is correct
73 Correct 12 ms 2584 KB Output is correct
74 Correct 13 ms 2716 KB Output is correct
75 Correct 11 ms 2588 KB Output is correct
76 Correct 25 ms 3820 KB Output is correct
77 Correct 22 ms 3756 KB Output is correct
78 Correct 22 ms 3664 KB Output is correct
79 Correct 22 ms 3668 KB Output is correct
80 Correct 22 ms 3664 KB Output is correct
81 Correct 45 ms 5920 KB Output is correct
82 Correct 44 ms 5924 KB Output is correct
83 Correct 45 ms 5900 KB Output is correct
84 Correct 45 ms 5824 KB Output is correct
85 Correct 45 ms 5824 KB Output is correct
86 Correct 48 ms 6048 KB Output is correct
87 Correct 49 ms 6076 KB Output is correct
88 Correct 48 ms 6012 KB Output is correct
89 Correct 49 ms 6020 KB Output is correct
90 Correct 51 ms 6072 KB Output is correct
91 Correct 87 ms 9132 KB Output is correct
92 Correct 80 ms 9328 KB Output is correct
93 Correct 80 ms 9272 KB Output is correct
94 Correct 82 ms 9116 KB Output is correct
95 Correct 79 ms 9140 KB Output is correct
96 Correct 84 ms 9784 KB Output is correct
97 Correct 90 ms 9644 KB Output is correct
98 Correct 85 ms 9784 KB Output is correct
99 Correct 91 ms 9812 KB Output is correct
100 Correct 84 ms 9808 KB Output is correct
101 Correct 84 ms 9760 KB Output is correct
102 Correct 85 ms 9784 KB Output is correct
103 Correct 86 ms 9780 KB Output is correct
104 Correct 99 ms 10044 KB Output is correct
105 Correct 84 ms 9784 KB Output is correct
106 Correct 85 ms 10040 KB Output is correct
107 Correct 85 ms 9964 KB Output is correct
108 Correct 84 ms 10036 KB Output is correct
109 Correct 84 ms 10872 KB Output is correct
110 Correct 84 ms 9932 KB Output is correct
111 Correct 84 ms 10080 KB Output is correct
112 Correct 85 ms 10036 KB Output is correct
113 Correct 89 ms 10348 KB Output is correct
114 Correct 94 ms 10036 KB Output is correct
115 Correct 84 ms 9852 KB Output is correct

Subtask #6
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1476 KB Output is correct
3 Correct 1 ms 1624 KB Output is correct
4 Correct 1 ms 1624 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1 ms 1484 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1636 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 1 ms 1628 KB Output is correct
13 Correct 2 ms 1628 KB Output is correct
14 Correct 12 ms 3492 KB Output is correct
15 Correct 18 ms 5320 KB Output is correct
16 Correct 29 ms 7832 KB Output is correct
17 Correct 26 ms 7736 KB Output is correct
18 Correct 30 ms 7780 KB Output is correct
19 Correct 39 ms 7764 KB Output is correct
20 Correct 35 ms 7660 KB Output is correct
21 Correct 27 ms 7736 KB Output is correct
22 Correct 28 ms 7732 KB Output is correct
23 Correct 39 ms 7636 KB Output is correct
24 Correct 29 ms 7784 KB Output is correct
25 Correct 28 ms 7604 KB Output is correct
26 Correct 1 ms 1628 KB Output is correct
27 Correct 1 ms 1628 KB Output is correct
28 Correct 2 ms 1628 KB Output is correct
29 Correct 11 ms 3408 KB Output is correct
30 Correct 30 ms 5316 KB Output is correct
31 Correct 31 ms 7988 KB Output is correct
32 Correct 41 ms 7920 KB Output is correct
33 Correct 31 ms 7944 KB Output is correct
34 Correct 31 ms 8000 KB Output is correct
35 Correct 32 ms 7920 KB Output is correct
36 Correct 45 ms 7736 KB Output is correct
37 Correct 31 ms 7856 KB Output is correct
38 Correct 30 ms 7724 KB Output is correct
39 Correct 32 ms 7740 KB Output is correct
40 Correct 40 ms 7960 KB Output is correct
41 Correct 1 ms 1628 KB Output is correct
42 Correct 1 ms 1520 KB Output is correct
43 Correct 1 ms 1628 KB Output is correct
44 Correct 3 ms 1628 KB Output is correct
45 Correct 2 ms 1628 KB Output is correct
46 Correct 3 ms 1624 KB Output is correct
47 Correct 9 ms 2520 KB Output is correct
48 Correct 10 ms 2588 KB Output is correct
49 Correct 19 ms 3556 KB Output is correct
50 Correct 39 ms 5556 KB Output is correct
51 Correct 57 ms 8208 KB Output is correct
52 Correct 56 ms 9016 KB Output is correct
53 Correct 63 ms 8264 KB Output is correct
54 Correct 58 ms 8252 KB Output is correct
55 Correct 58 ms 8292 KB Output is correct
56 Correct 58 ms 8248 KB Output is correct
57 Correct 57 ms 8172 KB Output is correct
58 Correct 56 ms 8272 KB Output is correct
59 Correct 60 ms 8352 KB Output is correct
60 Correct 57 ms 8336 KB Output is correct
61 Correct 70 ms 8288 KB Output is correct
62 Correct 59 ms 8112 KB Output is correct
63 Correct 57 ms 8296 KB Output is correct
64 Correct 57 ms 8296 KB Output is correct
65 Correct 74 ms 8244 KB Output is correct
66 Correct 70 ms 8248 KB Output is correct
67 Correct 75 ms 8244 KB Output is correct
68 Correct 56 ms 8244 KB Output is correct
69 Correct 57 ms 8308 KB Output is correct
70 Correct 57 ms 8116 KB Output is correct
71 Correct 12 ms 2584 KB Output is correct
72 Correct 11 ms 2588 KB Output is correct
73 Correct 12 ms 2584 KB Output is correct
74 Correct 13 ms 2716 KB Output is correct
75 Correct 11 ms 2588 KB Output is correct
76 Correct 25 ms 3820 KB Output is correct
77 Correct 22 ms 3756 KB Output is correct
78 Correct 22 ms 3664 KB Output is correct
79 Correct 22 ms 3668 KB Output is correct
80 Correct 22 ms 3664 KB Output is correct
81 Correct 45 ms 5920 KB Output is correct
82 Correct 44 ms 5924 KB Output is correct
83 Correct 45 ms 5900 KB Output is correct
84 Correct 45 ms 5824 KB Output is correct
85 Correct 45 ms 5824 KB Output is correct
86 Correct 48 ms 6048 KB Output is correct
87 Correct 49 ms 6076 KB Output is correct
88 Correct 48 ms 6012 KB Output is correct
89 Correct 49 ms 6020 KB Output is correct
90 Correct 51 ms 6072 KB Output is correct
91 Correct 87 ms 9132 KB Output is correct
92 Correct 80 ms 9328 KB Output is correct
93 Correct 80 ms 9272 KB Output is correct
94 Correct 82 ms 9116 KB Output is correct
95 Correct 79 ms 9140 KB Output is correct
96 Correct 84 ms 9784 KB Output is correct
97 Correct 90 ms 9644 KB Output is correct
98 Correct 85 ms 9784 KB Output is correct
99 Correct 91 ms 9812 KB Output is correct
100 Correct 84 ms 9808 KB Output is correct
101 Correct 84 ms 9760 KB Output is correct
102 Correct 85 ms 9784 KB Output is correct
103 Correct 86 ms 9780 KB Output is correct
104 Correct 99 ms 10044 KB Output is correct
105 Correct 84 ms 9784 KB Output is correct
106 Correct 85 ms 10040 KB Output is correct
107 Correct 85 ms 9964 KB Output is correct
108 Correct 84 ms 10036 KB Output is correct
109 Correct 84 ms 10872 KB Output is correct
110 Correct 84 ms 9932 KB Output is correct
111 Correct 84 ms 10080 KB Output is correct
112 Correct 85 ms 10036 KB Output is correct
113 Correct 89 ms 10348 KB Output is correct
114 Correct 94 ms 10036 KB Output is correct
115 Correct 84 ms 9852 KB Output is correct
116 Correct 268 ms 3776 KB Output is correct
117 Correct 398 ms 3772 KB Output is correct
118 Correct 463 ms 4740 KB Output is correct
119 Correct 734 ms 4676 KB Output is correct
120 Correct 640 ms 4664 KB Output is correct
121 Correct 1095 ms 5696 KB Output is correct
122 Correct 947 ms 5516 KB Output is correct
123 Correct 2308 ms 8084 KB Output is correct
124 Correct 1833 ms 8272 KB Output is correct
125 Correct 1544 ms 8316 KB Output is correct
126 Correct 2293 ms 10932 KB Output is correct
127 Correct 2351 ms 10584 KB Output is correct
128 Correct 2349 ms 10800 KB Output is correct
129 Correct 2350 ms 10796 KB Output is correct
130 Correct 2406 ms 10700 KB Output is correct
131 Correct 3259 ms 10796 KB Output is correct
132 Correct 3311 ms 11768 KB Output is correct
133 Correct 3128 ms 10756 KB Output is correct
134 Correct 3233 ms 10804 KB Output is correct
135 Correct 3258 ms 10756 KB Output is correct
136 Correct 3473 ms 10756 KB Output is correct
137 Correct 3272 ms 10780 KB Output is correct
138 Correct 3361 ms 10756 KB Output is correct
139 Correct 3272 ms 10740 KB Output is correct
140 Correct 3277 ms 10960 KB Output is correct
141 Correct 4064 ms 10788 KB Output is correct
142 Correct 4062 ms 10776 KB Output is correct
143 Correct 4097 ms 10784 KB Output is correct
144 Correct 4082 ms 10792 KB Output is correct
145 Correct 4102 ms 10784 KB Output is correct
146 Correct 3617 ms 11056 KB Output is correct
147 Correct 3639 ms 11032 KB Output is correct
148 Correct 3579 ms 11032 KB Output is correct
149 Correct 3643 ms 11048 KB Output is correct
150 Correct 3612 ms 11040 KB Output is correct
151 Correct 3150 ms 11072 KB Output is correct
152 Correct 3130 ms 11088 KB Output is correct
153 Correct 3185 ms 11076 KB Output is correct
154 Correct 3146 ms 12080 KB Output is correct
155 Correct 3135 ms 11060 KB Output is correct
156 Correct 2927 ms 11484 KB Output is correct
157 Correct 2956 ms 11484 KB Output is correct
158 Correct 2926 ms 11492 KB Output is correct
159 Correct 2952 ms 11564 KB Output is correct
160 Correct 2976 ms 11568 KB Output is correct
161 Correct 2003 ms 12532 KB Output is correct
162 Correct 2029 ms 11568 KB Output is correct
163 Correct 1965 ms 11592 KB Output is correct
164 Correct 2009 ms 11568 KB Output is correct
165 Correct 1970 ms 11592 KB Output is correct
166 Correct 2921 ms 11236 KB Output is correct
167 Correct 2970 ms 11248 KB Output is correct
168 Correct 2951 ms 11240 KB Output is correct
169 Correct 2898 ms 11236 KB Output is correct
170 Correct 2929 ms 11308 KB Output is correct
171 Correct 2205 ms 11328 KB Output is correct
172 Correct 2237 ms 11564 KB Output is correct
173 Correct 2201 ms 11316 KB Output is correct
174 Correct 2170 ms 11444 KB Output is correct
175 Correct 2248 ms 11356 KB Output is correct