답안 #867923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
867923	2023-10-29T19:58:09 Z	evenvalue	Diversity (CEOI21_diversity)	C++17	64 / 100	7000 ms	7224 KB

diversity

#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 map<int, int> &fof) {
  bool ceil = false;
  vector<repeat> left;
  vector<repeat> right;
  for (const auto [b, c] : fof) {
    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 map<int, int> &fof) {
  vector<repeat> repeats = simulate(fof);
  
  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);
    });

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

    vector<int> freq(kDistinct);
    map<int, int> fof; //frequency of frequencies
    
    fof[0] = kDistinct;

    auto add = [&](const int i) {
      const int f = freq[a[i]]++;
      fof[f]--;
      if (fof[f] == 0) fof.erase(f);
      fof[f + 1]++;
    };

    auto rem = [&](const int i) {
      const int f = freq[a[i]]--;
      fof[f]--;
      if (fof[f] == 0) fof.erase(f);
      fof[f - 1]++;
    };

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

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

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	408 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	2 ms	604 KB	Output is correct
4	Correct	16 ms	1504 KB	Output is correct
5	Correct	31 ms	2780 KB	Output is correct
6	Correct	51 ms	4092 KB	Output is correct
7	Correct	50 ms	4312 KB	Output is correct
8	Correct	60 ms	4312 KB	Output is correct
9	Correct	50 ms	4312 KB	Output is correct
10	Correct	51 ms	4312 KB	Output is correct
11	Correct	49 ms	4308 KB	Output is correct
12	Correct	51 ms	4328 KB	Output is correct
13	Correct	51 ms	4312 KB	Output is correct
14	Correct	50 ms	4308 KB	Output is correct
15	Correct	50 ms	4312 KB	Output is correct

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	2 ms	604 KB	Output is correct
4	Correct	16 ms	1504 KB	Output is correct
5	Correct	31 ms	2780 KB	Output is correct
6	Correct	51 ms	4092 KB	Output is correct
7	Correct	50 ms	4312 KB	Output is correct
8	Correct	60 ms	4312 KB	Output is correct
9	Correct	50 ms	4312 KB	Output is correct
10	Correct	51 ms	4312 KB	Output is correct
11	Correct	49 ms	4308 KB	Output is correct
12	Correct	51 ms	4328 KB	Output is correct
13	Correct	51 ms	4312 KB	Output is correct
14	Correct	50 ms	4308 KB	Output is correct
15	Correct	50 ms	4312 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	448 KB	Output is correct
18	Correct	2 ms	604 KB	Output is correct
19	Correct	19 ms	1760 KB	Output is correct
20	Correct	40 ms	2824 KB	Output is correct
21	Correct	58 ms	4564 KB	Output is correct
22	Correct	69 ms	4568 KB	Output is correct
23	Correct	58 ms	4568 KB	Output is correct
24	Correct	59 ms	4568 KB	Output is correct
25	Correct	61 ms	4564 KB	Output is correct
26	Correct	67 ms	4312 KB	Output is correct
27	Correct	59 ms	4556 KB	Output is correct
28	Correct	59 ms	4300 KB	Output is correct
29	Correct	60 ms	4312 KB	Output is correct
30	Correct	63 ms	4544 KB	Output is correct

Subtask #4
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	2 ms	604 KB	Output is correct
4	Correct	16 ms	1504 KB	Output is correct
5	Correct	31 ms	2780 KB	Output is correct
6	Correct	51 ms	4092 KB	Output is correct
7	Correct	50 ms	4312 KB	Output is correct
8	Correct	60 ms	4312 KB	Output is correct
9	Correct	50 ms	4312 KB	Output is correct
10	Correct	51 ms	4312 KB	Output is correct
11	Correct	49 ms	4308 KB	Output is correct
12	Correct	51 ms	4328 KB	Output is correct
13	Correct	51 ms	4312 KB	Output is correct
14	Correct	50 ms	4308 KB	Output is correct
15	Correct	50 ms	4312 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	448 KB	Output is correct
18	Correct	2 ms	604 KB	Output is correct
19	Correct	19 ms	1760 KB	Output is correct
20	Correct	40 ms	2824 KB	Output is correct
21	Correct	58 ms	4564 KB	Output is correct
22	Correct	69 ms	4568 KB	Output is correct
23	Correct	58 ms	4568 KB	Output is correct
24	Correct	59 ms	4568 KB	Output is correct
25	Correct	61 ms	4564 KB	Output is correct
26	Correct	67 ms	4312 KB	Output is correct
27	Correct	59 ms	4556 KB	Output is correct
28	Correct	59 ms	4300 KB	Output is correct
29	Correct	60 ms	4312 KB	Output is correct
30	Correct	63 ms	4544 KB	Output is correct
31	Correct	1 ms	344 KB	Output is correct
32	Correct	0 ms	348 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	3 ms	604 KB	Output is correct
35	Correct	3 ms	604 KB	Output is correct
36	Correct	2 ms	604 KB	Output is correct
37	Correct	14 ms	1188 KB	Output is correct
38	Correct	12 ms	1188 KB	Output is correct
39	Correct	27 ms	1756 KB	Output is correct
40	Correct	59 ms	2780 KB	Output is correct
41	Correct	92 ms	4568 KB	Output is correct
42	Correct	93 ms	4420 KB	Output is correct
43	Correct	95 ms	4560 KB	Output is correct
44	Correct	92 ms	4556 KB	Output is correct
45	Correct	91 ms	4564 KB	Output is correct
46	Correct	91 ms	4556 KB	Output is correct
47	Correct	103 ms	4680 KB	Output is correct
48	Correct	89 ms	4556 KB	Output is correct
49	Correct	93 ms	4568 KB	Output is correct
50	Correct	95 ms	4564 KB	Output is correct
51	Correct	97 ms	4568 KB	Output is correct
52	Correct	93 ms	4568 KB	Output is correct
53	Correct	95 ms	4556 KB	Output is correct
54	Correct	93 ms	4556 KB	Output is correct
55	Correct	90 ms	4564 KB	Output is correct
56	Correct	91 ms	4484 KB	Output is correct
57	Correct	91 ms	4464 KB	Output is correct
58	Correct	92 ms	4568 KB	Output is correct
59	Correct	93 ms	4572 KB	Output is correct
60	Correct	92 ms	4568 KB	Output is correct

Subtask #5
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	408 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	2 ms	604 KB	Output is correct
14	Correct	16 ms	1504 KB	Output is correct
15	Correct	31 ms	2780 KB	Output is correct
16	Correct	51 ms	4092 KB	Output is correct
17	Correct	50 ms	4312 KB	Output is correct
18	Correct	60 ms	4312 KB	Output is correct
19	Correct	50 ms	4312 KB	Output is correct
20	Correct	51 ms	4312 KB	Output is correct
21	Correct	49 ms	4308 KB	Output is correct
22	Correct	51 ms	4328 KB	Output is correct
23	Correct	51 ms	4312 KB	Output is correct
24	Correct	50 ms	4308 KB	Output is correct
25	Correct	50 ms	4312 KB	Output is correct
26	Correct	1 ms	348 KB	Output is correct
27	Correct	1 ms	448 KB	Output is correct
28	Correct	2 ms	604 KB	Output is correct
29	Correct	19 ms	1760 KB	Output is correct
30	Correct	40 ms	2824 KB	Output is correct
31	Correct	58 ms	4564 KB	Output is correct
32	Correct	69 ms	4568 KB	Output is correct
33	Correct	58 ms	4568 KB	Output is correct
34	Correct	59 ms	4568 KB	Output is correct
35	Correct	61 ms	4564 KB	Output is correct
36	Correct	67 ms	4312 KB	Output is correct
37	Correct	59 ms	4556 KB	Output is correct
38	Correct	59 ms	4300 KB	Output is correct
39	Correct	60 ms	4312 KB	Output is correct
40	Correct	63 ms	4544 KB	Output is correct
41	Correct	1 ms	344 KB	Output is correct
42	Correct	0 ms	348 KB	Output is correct
43	Correct	0 ms	348 KB	Output is correct
44	Correct	3 ms	604 KB	Output is correct
45	Correct	3 ms	604 KB	Output is correct
46	Correct	2 ms	604 KB	Output is correct
47	Correct	14 ms	1188 KB	Output is correct
48	Correct	12 ms	1188 KB	Output is correct
49	Correct	27 ms	1756 KB	Output is correct
50	Correct	59 ms	2780 KB	Output is correct
51	Correct	92 ms	4568 KB	Output is correct
52	Correct	93 ms	4420 KB	Output is correct
53	Correct	95 ms	4560 KB	Output is correct
54	Correct	92 ms	4556 KB	Output is correct
55	Correct	91 ms	4564 KB	Output is correct
56	Correct	91 ms	4556 KB	Output is correct
57	Correct	103 ms	4680 KB	Output is correct
58	Correct	89 ms	4556 KB	Output is correct
59	Correct	93 ms	4568 KB	Output is correct
60	Correct	95 ms	4564 KB	Output is correct
61	Correct	97 ms	4568 KB	Output is correct
62	Correct	93 ms	4568 KB	Output is correct
63	Correct	95 ms	4556 KB	Output is correct
64	Correct	93 ms	4556 KB	Output is correct
65	Correct	90 ms	4564 KB	Output is correct
66	Correct	91 ms	4484 KB	Output is correct
67	Correct	91 ms	4464 KB	Output is correct
68	Correct	92 ms	4568 KB	Output is correct
69	Correct	93 ms	4572 KB	Output is correct
70	Correct	92 ms	4568 KB	Output is correct
71	Correct	12 ms	1116 KB	Output is correct
72	Correct	12 ms	1116 KB	Output is correct
73	Correct	12 ms	1472 KB	Output is correct
74	Correct	12 ms	1208 KB	Output is correct
75	Correct	12 ms	1240 KB	Output is correct
76	Correct	26 ms	1760 KB	Output is correct
77	Correct	23 ms	1760 KB	Output is correct
78	Correct	25 ms	1972 KB	Output is correct
79	Correct	24 ms	1756 KB	Output is correct
80	Correct	23 ms	1760 KB	Output is correct
81	Correct	50 ms	3036 KB	Output is correct
82	Correct	52 ms	3024 KB	Output is correct
83	Correct	49 ms	3024 KB	Output is correct
84	Correct	51 ms	3288 KB	Output is correct
85	Correct	48 ms	3036 KB	Output is correct
86	Correct	48 ms	3032 KB	Output is correct
87	Correct	49 ms	3032 KB	Output is correct
88	Correct	48 ms	2972 KB	Output is correct
89	Correct	50 ms	3032 KB	Output is correct
90	Correct	51 ms	3128 KB	Output is correct
91	Correct	86 ms	4820 KB	Output is correct
92	Correct	76 ms	4816 KB	Output is correct
93	Correct	80 ms	4824 KB	Output is correct
94	Correct	76 ms	4820 KB	Output is correct
95	Correct	77 ms	4764 KB	Output is correct
96	Correct	81 ms	5080 KB	Output is correct
97	Correct	79 ms	5068 KB	Output is correct
98	Correct	81 ms	5080 KB	Output is correct
99	Correct	94 ms	5072 KB	Output is correct
100	Correct	82 ms	5068 KB	Output is correct
101	Correct	80 ms	4988 KB	Output is correct
102	Correct	80 ms	4880 KB	Output is correct
103	Correct	81 ms	5080 KB	Output is correct
104	Correct	80 ms	5080 KB	Output is correct
105	Correct	81 ms	5072 KB	Output is correct
106	Correct	84 ms	5080 KB	Output is correct
107	Correct	79 ms	5080 KB	Output is correct
108	Correct	82 ms	5000 KB	Output is correct
109	Correct	81 ms	5080 KB	Output is correct
110	Correct	81 ms	5080 KB	Output is correct
111	Correct	81 ms	5072 KB	Output is correct
112	Correct	80 ms	5080 KB	Output is correct
113	Correct	83 ms	5196 KB	Output is correct
114	Correct	80 ms	5072 KB	Output is correct
115	Correct	82 ms	5076 KB	Output is correct

Subtask #6
0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	408 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	2 ms	604 KB	Output is correct
14	Correct	16 ms	1504 KB	Output is correct
15	Correct	31 ms	2780 KB	Output is correct
16	Correct	51 ms	4092 KB	Output is correct
17	Correct	50 ms	4312 KB	Output is correct
18	Correct	60 ms	4312 KB	Output is correct
19	Correct	50 ms	4312 KB	Output is correct
20	Correct	51 ms	4312 KB	Output is correct
21	Correct	49 ms	4308 KB	Output is correct
22	Correct	51 ms	4328 KB	Output is correct
23	Correct	51 ms	4312 KB	Output is correct
24	Correct	50 ms	4308 KB	Output is correct
25	Correct	50 ms	4312 KB	Output is correct
26	Correct	1 ms	348 KB	Output is correct
27	Correct	1 ms	448 KB	Output is correct
28	Correct	2 ms	604 KB	Output is correct
29	Correct	19 ms	1760 KB	Output is correct
30	Correct	40 ms	2824 KB	Output is correct
31	Correct	58 ms	4564 KB	Output is correct
32	Correct	69 ms	4568 KB	Output is correct
33	Correct	58 ms	4568 KB	Output is correct
34	Correct	59 ms	4568 KB	Output is correct
35	Correct	61 ms	4564 KB	Output is correct
36	Correct	67 ms	4312 KB	Output is correct
37	Correct	59 ms	4556 KB	Output is correct
38	Correct	59 ms	4300 KB	Output is correct
39	Correct	60 ms	4312 KB	Output is correct
40	Correct	63 ms	4544 KB	Output is correct
41	Correct	1 ms	344 KB	Output is correct
42	Correct	0 ms	348 KB	Output is correct
43	Correct	0 ms	348 KB	Output is correct
44	Correct	3 ms	604 KB	Output is correct
45	Correct	3 ms	604 KB	Output is correct
46	Correct	2 ms	604 KB	Output is correct
47	Correct	14 ms	1188 KB	Output is correct
48	Correct	12 ms	1188 KB	Output is correct
49	Correct	27 ms	1756 KB	Output is correct
50	Correct	59 ms	2780 KB	Output is correct
51	Correct	92 ms	4568 KB	Output is correct
52	Correct	93 ms	4420 KB	Output is correct
53	Correct	95 ms	4560 KB	Output is correct
54	Correct	92 ms	4556 KB	Output is correct
55	Correct	91 ms	4564 KB	Output is correct
56	Correct	91 ms	4556 KB	Output is correct
57	Correct	103 ms	4680 KB	Output is correct
58	Correct	89 ms	4556 KB	Output is correct
59	Correct	93 ms	4568 KB	Output is correct
60	Correct	95 ms	4564 KB	Output is correct
61	Correct	97 ms	4568 KB	Output is correct
62	Correct	93 ms	4568 KB	Output is correct
63	Correct	95 ms	4556 KB	Output is correct
64	Correct	93 ms	4556 KB	Output is correct
65	Correct	90 ms	4564 KB	Output is correct
66	Correct	91 ms	4484 KB	Output is correct
67	Correct	91 ms	4464 KB	Output is correct
68	Correct	92 ms	4568 KB	Output is correct
69	Correct	93 ms	4572 KB	Output is correct
70	Correct	92 ms	4568 KB	Output is correct
71	Correct	12 ms	1116 KB	Output is correct
72	Correct	12 ms	1116 KB	Output is correct
73	Correct	12 ms	1472 KB	Output is correct
74	Correct	12 ms	1208 KB	Output is correct
75	Correct	12 ms	1240 KB	Output is correct
76	Correct	26 ms	1760 KB	Output is correct
77	Correct	23 ms	1760 KB	Output is correct
78	Correct	25 ms	1972 KB	Output is correct
79	Correct	24 ms	1756 KB	Output is correct
80	Correct	23 ms	1760 KB	Output is correct
81	Correct	50 ms	3036 KB	Output is correct
82	Correct	52 ms	3024 KB	Output is correct
83	Correct	49 ms	3024 KB	Output is correct
84	Correct	51 ms	3288 KB	Output is correct
85	Correct	48 ms	3036 KB	Output is correct
86	Correct	48 ms	3032 KB	Output is correct
87	Correct	49 ms	3032 KB	Output is correct
88	Correct	48 ms	2972 KB	Output is correct
89	Correct	50 ms	3032 KB	Output is correct
90	Correct	51 ms	3128 KB	Output is correct
91	Correct	86 ms	4820 KB	Output is correct
92	Correct	76 ms	4816 KB	Output is correct
93	Correct	80 ms	4824 KB	Output is correct
94	Correct	76 ms	4820 KB	Output is correct
95	Correct	77 ms	4764 KB	Output is correct
96	Correct	81 ms	5080 KB	Output is correct
97	Correct	79 ms	5068 KB	Output is correct
98	Correct	81 ms	5080 KB	Output is correct
99	Correct	94 ms	5072 KB	Output is correct
100	Correct	82 ms	5068 KB	Output is correct
101	Correct	80 ms	4988 KB	Output is correct
102	Correct	80 ms	4880 KB	Output is correct
103	Correct	81 ms	5080 KB	Output is correct
104	Correct	80 ms	5080 KB	Output is correct
105	Correct	81 ms	5072 KB	Output is correct
106	Correct	84 ms	5080 KB	Output is correct
107	Correct	79 ms	5080 KB	Output is correct
108	Correct	82 ms	5000 KB	Output is correct
109	Correct	81 ms	5080 KB	Output is correct
110	Correct	81 ms	5080 KB	Output is correct
111	Correct	81 ms	5072 KB	Output is correct
112	Correct	80 ms	5080 KB	Output is correct
113	Correct	83 ms	5196 KB	Output is correct
114	Correct	80 ms	5072 KB	Output is correct
115	Correct	82 ms	5076 KB	Output is correct
116	Correct	1152 ms	2848 KB	Output is correct
117	Correct	1004 ms	3116 KB	Output is correct
118	Correct	1814 ms	3424 KB	Output is correct
119	Correct	1325 ms	3428 KB	Output is correct
120	Correct	896 ms	3468 KB	Output is correct
121	Correct	2105 ms	4460 KB	Output is correct
122	Correct	1436 ms	4460 KB	Output is correct
123	Correct	6074 ms	6264 KB	Output is correct
124	Correct	2866 ms	6808 KB	Output is correct
125	Correct	2028 ms	6840 KB	Output is correct
126	Execution timed out	7042 ms	7224 KB	Time limit exceeded
127	Halted	0 ms	0 KB	-

답안 #867923

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 10.0 / 10.0

Subtask #3 8.0 / 8.0

Subtask #4 16.0 / 16.0

Subtask #5 26.0 / 26.0

Subtask #6 0 / 36.0

Subtask #1
4.0 / 4.0

Subtask #2
10.0 / 10.0

Subtask #3
8.0 / 8.0

Subtask #4
16.0 / 16.0

Subtask #5
26.0 / 26.0

Subtask #6
0 / 36.0