oj.uz

Submission #799399

# Submission time Handle Problem Language Result Execution time Memory
799399 2023-07-31T13:50:00 Z Johann Diversity (CEOI21_diversity) C++14
64 / 100
 7000 ms 14412 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const ll INF = 1e18;
int N, Q;
vi A;
vi ans;
vi freq;
ll tmp, pref, suff, n;

struct query
{
    int l, r, idx;
};

ll numberOfSubsequences(ll x)
{
    return x * (x + 1) / 2;
}
ll totalLengthOfSubsequences(ll x)
{
    return x * (x + 1) * (x + 1) / 2 - (2 * x + 1) * (x + 1) * x / 6;
}
void doStuff(ll x, ll y)
{
    ll len = x * y;

    // if both are in set
    tmp -= totalLengthOfSubsequences(len) - x * x * (totalLengthOfSubsequences(y) - y) - y * numberOfSubsequences(x);
    // if one is inside the other isn't
    tmp -= (n - len) * (len * (len + 1) / 2 - x * y * (y + 1) / 2);
    // if both are outside
    tmp -= (len - y) * pref * (n - pref - len);

    pref += len;
    swap(pref, suff);
}
struct segtree
{
    vi arr;
    int size;
    void init(int _size)
    {
        size = 1;
        while (size < _size)
            size *= 2;
        arr.assign(2 * size, 0);
    }
    void add(int i, int v)
    {
        i += size;
        while (i > 0)
        {
            arr[i] += v;
            i /= 2;
        }
    }
    void dfs(int x)
    {
        if (arr[x] == 0)
            return;
        if (x < size)
        {
            dfs(2 * x);
            dfs(2 * x + 1);
        }
        else
        {
            // arr[x] := how often
            if (arr[x] & 1)
                doStuff(x - size, 1);
            if (arr[x] > 1)
            {
                doStuff(x - size, arr[x] / 2);
                doStuff(x - size, arr[x] / 2);
            }
        }
    }
};
segtree seg;
void add(int x)
{
    if (freq[x] > 0)
        seg.add(freq[x], -1);
    ++freq[x];
    seg.add(freq[x], 1);
}
void sub(int x)
{
    seg.add(freq[x], -1);
    --freq[x];
    if (freq[x])
        seg.add(freq[x], 1);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> Q;
    A.resize(N);
    for (int i = 0; i < N; ++i)
        cin >> A[i];

    vector<query> Qu(Q);
    ans.resize(Q);
    for (int i = 0; i < Q; ++i)
        cin >> Qu[i].l >> Qu[i].r, Qu[i].idx = i, --Qu[i].l;

    int sq = 1;
    while (sq * sq < N)
        ++sq;
    auto cmp = [&](const query &a, const query &b)
    { if (a.l / sq == b.l / sq) 
        return a.r < b.r;
    else
        return a.l < b.l; };
    sort(all(Qu), cmp);

    int lx = 0, rx = 0;
    freq.assign(*max_element(all(A)) + 1, 0);
    seg.init(N + 1);
    for (query q : Qu)
    {
        while (rx < q.r)
            add(A[rx++]);
        while (lx > q.l)
            add(A[--lx]);
        while (rx > q.r)
            sub(A[--rx]);
        while (lx < q.l)
            sub(A[lx++]);

        n = q.r - q.l;
        pref = 0, suff = 0;
        tmp = totalLengthOfSubsequences(n);

        seg.dfs(1);

        ans[q.idx] = tmp;
    }
    for (ll x : ans)
        cout << x << "\n";

    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 7 ms 3284 KB Output is correct
5 Correct 15 ms 6192 KB Output is correct
6 Correct 27 ms 11232 KB Output is correct
7 Correct 25 ms 11040 KB Output is correct
8 Correct 23 ms 11092 KB Output is correct
9 Correct 30 ms 11060 KB Output is correct
10 Correct 30 ms 11072 KB Output is correct
11 Correct 24 ms 11076 KB Output is correct
12 Correct 25 ms 11076 KB Output is correct
13 Correct 25 ms 11124 KB Output is correct
14 Correct 24 ms 11092 KB Output is correct
15 Correct 29 ms 11080 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 7 ms 3284 KB Output is correct
5 Correct 15 ms 6192 KB Output is correct
6 Correct 27 ms 11232 KB Output is correct
7 Correct 25 ms 11040 KB Output is correct
8 Correct 23 ms 11092 KB Output is correct
9 Correct 30 ms 11060 KB Output is correct
10 Correct 30 ms 11072 KB Output is correct
11 Correct 24 ms 11076 KB Output is correct
12 Correct 25 ms 11076 KB Output is correct
13 Correct 25 ms 11124 KB Output is correct
14 Correct 24 ms 11092 KB Output is correct
15 Correct 29 ms 11080 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 8 ms 3412 KB Output is correct
20 Correct 16 ms 6244 KB Output is correct
21 Correct 24 ms 11016 KB Output is correct
22 Correct 26 ms 11040 KB Output is correct
23 Correct 25 ms 11008 KB Output is correct
24 Correct 25 ms 11092 KB Output is correct
25 Correct 26 ms 11132 KB Output is correct
26 Correct 26 ms 11104 KB Output is correct
27 Correct 26 ms 11004 KB Output is correct
28 Correct 26 ms 11060 KB Output is correct
29 Correct 26 ms 11040 KB Output is correct
30 Correct 26 ms 11124 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 7 ms 3284 KB Output is correct
5 Correct 15 ms 6192 KB Output is correct
6 Correct 27 ms 11232 KB Output is correct
7 Correct 25 ms 11040 KB Output is correct
8 Correct 23 ms 11092 KB Output is correct
9 Correct 30 ms 11060 KB Output is correct
10 Correct 30 ms 11072 KB Output is correct
11 Correct 24 ms 11076 KB Output is correct
12 Correct 25 ms 11076 KB Output is correct
13 Correct 25 ms 11124 KB Output is correct
14 Correct 24 ms 11092 KB Output is correct
15 Correct 29 ms 11080 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 8 ms 3412 KB Output is correct
20 Correct 16 ms 6244 KB Output is correct
21 Correct 24 ms 11016 KB Output is correct
22 Correct 26 ms 11040 KB Output is correct
23 Correct 25 ms 11008 KB Output is correct
24 Correct 25 ms 11092 KB Output is correct
25 Correct 26 ms 11132 KB Output is correct
26 Correct 26 ms 11104 KB Output is correct
27 Correct 26 ms 11004 KB Output is correct
28 Correct 26 ms 11060 KB Output is correct
29 Correct 26 ms 11040 KB Output is correct
30 Correct 26 ms 11124 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 316 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 584 KB Output is correct
35 Correct 2 ms 568 KB Output is correct
36 Correct 1 ms 724 KB Output is correct
37 Correct 4 ms 1876 KB Output is correct
38 Correct 5 ms 1868 KB Output is correct
39 Correct 9 ms 3412 KB Output is correct
40 Correct 18 ms 6220 KB Output is correct
41 Correct 32 ms 11120 KB Output is correct
42 Correct 29 ms 11100 KB Output is correct
43 Correct 31 ms 11064 KB Output is correct
44 Correct 29 ms 11020 KB Output is correct
45 Correct 29 ms 11132 KB Output is correct
46 Correct 28 ms 11060 KB Output is correct
47 Correct 28 ms 11128 KB Output is correct
48 Correct 30 ms 11068 KB Output is correct
49 Correct 28 ms 11124 KB Output is correct
50 Correct 28 ms 11024 KB Output is correct
51 Correct 31 ms 11092 KB Output is correct
52 Correct 30 ms 11136 KB Output is correct
53 Correct 28 ms 11008 KB Output is correct
54 Correct 29 ms 11032 KB Output is correct
55 Correct 29 ms 11060 KB Output is correct
56 Correct 29 ms 11108 KB Output is correct
57 Correct 29 ms 11104 KB Output is correct
58 Correct 28 ms 11044 KB Output is correct
59 Correct 30 ms 11060 KB Output is correct
60 Correct 31 ms 11044 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 588 KB Output is correct
14 Correct 7 ms 3284 KB Output is correct
15 Correct 15 ms 6192 KB Output is correct
16 Correct 27 ms 11232 KB Output is correct
17 Correct 25 ms 11040 KB Output is correct
18 Correct 23 ms 11092 KB Output is correct
19 Correct 30 ms 11060 KB Output is correct
20 Correct 30 ms 11072 KB Output is correct
21 Correct 24 ms 11076 KB Output is correct
22 Correct 25 ms 11076 KB Output is correct
23 Correct 25 ms 11124 KB Output is correct
24 Correct 24 ms 11092 KB Output is correct
25 Correct 29 ms 11080 KB Output is correct
26 Correct 1 ms 256 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 8 ms 3412 KB Output is correct
30 Correct 16 ms 6244 KB Output is correct
31 Correct 24 ms 11016 KB Output is correct
32 Correct 26 ms 11040 KB Output is correct
33 Correct 25 ms 11008 KB Output is correct
34 Correct 25 ms 11092 KB Output is correct
35 Correct 26 ms 11132 KB Output is correct
36 Correct 26 ms 11104 KB Output is correct
37 Correct 26 ms 11004 KB Output is correct
38 Correct 26 ms 11060 KB Output is correct
39 Correct 26 ms 11040 KB Output is correct
40 Correct 26 ms 11124 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 1 ms 316 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 1 ms 584 KB Output is correct
45 Correct 2 ms 568 KB Output is correct
46 Correct 1 ms 724 KB Output is correct
47 Correct 4 ms 1876 KB Output is correct
48 Correct 5 ms 1868 KB Output is correct
49 Correct 9 ms 3412 KB Output is correct
50 Correct 18 ms 6220 KB Output is correct
51 Correct 32 ms 11120 KB Output is correct
52 Correct 29 ms 11100 KB Output is correct
53 Correct 31 ms 11064 KB Output is correct
54 Correct 29 ms 11020 KB Output is correct
55 Correct 29 ms 11132 KB Output is correct
56 Correct 28 ms 11060 KB Output is correct
57 Correct 28 ms 11128 KB Output is correct
58 Correct 30 ms 11068 KB Output is correct
59 Correct 28 ms 11124 KB Output is correct
60 Correct 28 ms 11024 KB Output is correct
61 Correct 31 ms 11092 KB Output is correct
62 Correct 30 ms 11136 KB Output is correct
63 Correct 28 ms 11008 KB Output is correct
64 Correct 29 ms 11032 KB Output is correct
65 Correct 29 ms 11060 KB Output is correct
66 Correct 29 ms 11108 KB Output is correct
67 Correct 29 ms 11104 KB Output is correct
68 Correct 28 ms 11044 KB Output is correct
69 Correct 30 ms 11060 KB Output is correct
70 Correct 31 ms 11044 KB Output is correct
71 Correct 5 ms 1876 KB Output is correct
72 Correct 5 ms 1984 KB Output is correct
73 Correct 5 ms 1844 KB Output is correct
74 Correct 5 ms 1864 KB Output is correct
75 Correct 5 ms 1876 KB Output is correct
76 Correct 11 ms 3416 KB Output is correct
77 Correct 11 ms 3436 KB Output is correct
78 Correct 10 ms 3400 KB Output is correct
79 Correct 10 ms 3420 KB Output is correct
80 Correct 11 ms 3408 KB Output is correct
81 Correct 26 ms 6332 KB Output is correct
82 Correct 23 ms 6344 KB Output is correct
83 Correct 24 ms 6348 KB Output is correct
84 Correct 24 ms 6276 KB Output is correct
85 Correct 24 ms 6292 KB Output is correct
86 Correct 29 ms 6496 KB Output is correct
87 Correct 28 ms 6484 KB Output is correct
88 Correct 35 ms 6432 KB Output is correct
89 Correct 29 ms 6436 KB Output is correct
90 Correct 29 ms 6432 KB Output is correct
91 Correct 57 ms 11980 KB Output is correct
92 Correct 58 ms 12036 KB Output is correct
93 Correct 57 ms 11948 KB Output is correct
94 Correct 59 ms 12016 KB Output is correct
95 Correct 58 ms 12012 KB Output is correct
96 Correct 54 ms 12820 KB Output is correct
97 Correct 55 ms 12728 KB Output is correct
98 Correct 59 ms 12724 KB Output is correct
99 Correct 55 ms 12772 KB Output is correct
100 Correct 56 ms 12748 KB Output is correct
101 Correct 55 ms 12776 KB Output is correct
102 Correct 55 ms 12720 KB Output is correct
103 Correct 58 ms 12820 KB Output is correct
104 Correct 57 ms 12760 KB Output is correct
105 Correct 54 ms 12800 KB Output is correct
106 Correct 51 ms 13116 KB Output is correct
107 Correct 52 ms 13132 KB Output is correct
108 Correct 52 ms 13004 KB Output is correct
109 Correct 55 ms 13084 KB Output is correct
110 Correct 51 ms 13096 KB Output is correct
111 Correct 58 ms 13088 KB Output is correct
112 Correct 56 ms 13056 KB Output is correct
113 Correct 55 ms 13040 KB Output is correct
114 Correct 52 ms 13048 KB Output is correct
115 Correct 54 ms 13104 KB Output is correct

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 588 KB Output is correct
14 Correct 7 ms 3284 KB Output is correct
15 Correct 15 ms 6192 KB Output is correct
16 Correct 27 ms 11232 KB Output is correct
17 Correct 25 ms 11040 KB Output is correct
18 Correct 23 ms 11092 KB Output is correct
19 Correct 30 ms 11060 KB Output is correct
20 Correct 30 ms 11072 KB Output is correct
21 Correct 24 ms 11076 KB Output is correct
22 Correct 25 ms 11076 KB Output is correct
23 Correct 25 ms 11124 KB Output is correct
24 Correct 24 ms 11092 KB Output is correct
25 Correct 29 ms 11080 KB Output is correct
26 Correct 1 ms 256 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 8 ms 3412 KB Output is correct
30 Correct 16 ms 6244 KB Output is correct
31 Correct 24 ms 11016 KB Output is correct
32 Correct 26 ms 11040 KB Output is correct
33 Correct 25 ms 11008 KB Output is correct
34 Correct 25 ms 11092 KB Output is correct
35 Correct 26 ms 11132 KB Output is correct
36 Correct 26 ms 11104 KB Output is correct
37 Correct 26 ms 11004 KB Output is correct
38 Correct 26 ms 11060 KB Output is correct
39 Correct 26 ms 11040 KB Output is correct
40 Correct 26 ms 11124 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 1 ms 316 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 1 ms 584 KB Output is correct
45 Correct 2 ms 568 KB Output is correct
46 Correct 1 ms 724 KB Output is correct
47 Correct 4 ms 1876 KB Output is correct
48 Correct 5 ms 1868 KB Output is correct
49 Correct 9 ms 3412 KB Output is correct
50 Correct 18 ms 6220 KB Output is correct
51 Correct 32 ms 11120 KB Output is correct
52 Correct 29 ms 11100 KB Output is correct
53 Correct 31 ms 11064 KB Output is correct
54 Correct 29 ms 11020 KB Output is correct
55 Correct 29 ms 11132 KB Output is correct
56 Correct 28 ms 11060 KB Output is correct
57 Correct 28 ms 11128 KB Output is correct
58 Correct 30 ms 11068 KB Output is correct
59 Correct 28 ms 11124 KB Output is correct
60 Correct 28 ms 11024 KB Output is correct
61 Correct 31 ms 11092 KB Output is correct
62 Correct 30 ms 11136 KB Output is correct
63 Correct 28 ms 11008 KB Output is correct
64 Correct 29 ms 11032 KB Output is correct
65 Correct 29 ms 11060 KB Output is correct
66 Correct 29 ms 11108 KB Output is correct
67 Correct 29 ms 11104 KB Output is correct
68 Correct 28 ms 11044 KB Output is correct
69 Correct 30 ms 11060 KB Output is correct
70 Correct 31 ms 11044 KB Output is correct
71 Correct 5 ms 1876 KB Output is correct
72 Correct 5 ms 1984 KB Output is correct
73 Correct 5 ms 1844 KB Output is correct
74 Correct 5 ms 1864 KB Output is correct
75 Correct 5 ms 1876 KB Output is correct
76 Correct 11 ms 3416 KB Output is correct
77 Correct 11 ms 3436 KB Output is correct
78 Correct 10 ms 3400 KB Output is correct
79 Correct 10 ms 3420 KB Output is correct
80 Correct 11 ms 3408 KB Output is correct
81 Correct 26 ms 6332 KB Output is correct
82 Correct 23 ms 6344 KB Output is correct
83 Correct 24 ms 6348 KB Output is correct
84 Correct 24 ms 6276 KB Output is correct
85 Correct 24 ms 6292 KB Output is correct
86 Correct 29 ms 6496 KB Output is correct
87 Correct 28 ms 6484 KB Output is correct
88 Correct 35 ms 6432 KB Output is correct
89 Correct 29 ms 6436 KB Output is correct
90 Correct 29 ms 6432 KB Output is correct
91 Correct 57 ms 11980 KB Output is correct
92 Correct 58 ms 12036 KB Output is correct
93 Correct 57 ms 11948 KB Output is correct
94 Correct 59 ms 12016 KB Output is correct
95 Correct 58 ms 12012 KB Output is correct
96 Correct 54 ms 12820 KB Output is correct
97 Correct 55 ms 12728 KB Output is correct
98 Correct 59 ms 12724 KB Output is correct
99 Correct 55 ms 12772 KB Output is correct
100 Correct 56 ms 12748 KB Output is correct
101 Correct 55 ms 12776 KB Output is correct
102 Correct 55 ms 12720 KB Output is correct
103 Correct 58 ms 12820 KB Output is correct
104 Correct 57 ms 12760 KB Output is correct
105 Correct 54 ms 12800 KB Output is correct
106 Correct 51 ms 13116 KB Output is correct
107 Correct 52 ms 13132 KB Output is correct
108 Correct 52 ms 13004 KB Output is correct
109 Correct 55 ms 13084 KB Output is correct
110 Correct 51 ms 13096 KB Output is correct
111 Correct 58 ms 13088 KB Output is correct
112 Correct 56 ms 13056 KB Output is correct
113 Correct 55 ms 13040 KB Output is correct
114 Correct 52 ms 13048 KB Output is correct
115 Correct 54 ms 13104 KB Output is correct
116 Correct 119 ms 2296 KB Output is correct
117 Correct 131 ms 2288 KB Output is correct
118 Correct 432 ms 3480 KB Output is correct
119 Correct 461 ms 3500 KB Output is correct
120 Correct 450 ms 3492 KB Output is correct
121 Correct 1149 ms 4908 KB Output is correct
122 Correct 1238 ms 4976 KB Output is correct
123 Correct 3066 ms 7868 KB Output is correct
124 Correct 4922 ms 7904 KB Output is correct
125 Correct 6411 ms 7944 KB Output is correct
126 Correct 4672 ms 12620 KB Output is correct
127 Correct 4806 ms 14092 KB Output is correct
128 Correct 4898 ms 14088 KB Output is correct
129 Correct 4990 ms 14096 KB Output is correct
130 Correct 4634 ms 14088 KB Output is correct
131 Correct 5091 ms 14260 KB Output is correct
132 Correct 5965 ms 14260 KB Output is correct
133 Correct 5360 ms 14244 KB Output is correct
134 Correct 6069 ms 14256 KB Output is correct
135 Correct 5066 ms 14268 KB Output is correct
136 Correct 5066 ms 14260 KB Output is correct
137 Correct 5153 ms 14276 KB Output is correct
138 Correct 5149 ms 14248 KB Output is correct
139 Correct 5050 ms 14256 KB Output is correct
140 Correct 5047 ms 14348 KB Output is correct
141 Correct 5980 ms 14292 KB Output is correct
142 Correct 5982 ms 14380 KB Output is correct
143 Correct 5958 ms 14288 KB Output is correct
144 Correct 5975 ms 14292 KB Output is correct
145 Correct 5962 ms 14412 KB Output is correct
146 Execution timed out 7075 ms 13916 KB Time limit exceeded
147 Halted 0 ms 0 KB -