oj.uz

Submission #650647

# Submission time Handle Problem Language Result Execution time Memory
650647 2022-10-14T11:39:19 Z 1bin Diversity (CEOI21_diversity) C++14
4 / 100
 15 ms 1492 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 3e5 + 5;
const int b = 550;
ll n, Q, a[NMAX], ans[NMAX], l, r, c[NMAX], cnt[NMAX], ls, rs, x, y, res;
map<int, int> mp;
struct query{
    int i, l, r;
    bool operator <(const query& x){
        if(l / b == x.l / b) return (l / b & 1) ? r > x.r : r < x.r;
        else return l / b < x.l / b;
    }
} q[NMAX];

void f(int x, int v){
    if(--mp[c[x]] == 0) mp.erase(c[x]);
    cnt[c[x]]--;
    c[x] += v;
    mp[c[x]] = ++cnt[c[x]];
    //for(int i = 1; i <= 3; i++) cout << cnt[i] << ' ';
    //cout << '\n';
    return;
}

ll cal(ll l, ll x, ll c){ return x * (x + 1) * (2 * x + 1) / 6 * c * c + c * (l - c) * x * (x + 1) + (l - c) * (l - c) * x;}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> Q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 0; i < Q; i++) cin >> q[i].l >> q[i].r, q[i].i = i;
    sort(q, q + Q);
    l = 1, r = 0;
    for(int i = 0; i < Q; i++){
        while(l > q[i].l) f(a[--l], 1);
        while(r < q[i].r) f(a[++r], 1);
        while(l < q[i].l) f(a[l++], -1);
        while(r > q[i].r) f(a[r--], -1);
        ls = rs = res = 0;
        //cout << "start qury \n";
        for(auto& [c, t] : mp){
            if(!c) continue;
            x = (t + 1) / 2; y = t - x;
            int n = r - l + 1;
            //cout << c << ' ' << t << '\n';
            res += (n * n + c) * t;
            res -= cal(ls, x, c) + cal(n - ls - c - (x - 1) * c, x, c);
            res -= cal(rs, y, c) + cal(n - rs - c - (y - 1) * c, y, c);
            ls += x * c; rs += y * c;
            if(x > y) swap(ls, rs);
        }
        ans[q[i].i] = res / 2;
    }
    
    for(int i = 0; i < Q; i++) cout << ans[i] << '\n';
    return 0;
}

Compilation message

diversity.cpp: In function 'int main()':
diversity.cpp:46:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |         for(auto& [c, t] : mp){
      |                   ^

Subtask #1
4.0 / 4.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Incorrect 15 ms 1492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Incorrect 15 ms 1492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Incorrect 15 ms 1492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Incorrect 15 ms 1492 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Incorrect 15 ms 1492 KB Output isn't correct
15 Halted 0 ms 0 KB -