Submission #551321

#	Time	Username	Problem	Language	Result	Execution time	Memory
551321		apostoldaniel854	Diversity (CEOI21_diversity)	C++14	64 / 100	7089 ms	16412 KiB

diversity

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define dbg(x) cerr << #x << " " << x << "\n"

const int MAX_N = 3e5;
int n, Q;
int a[1 + MAX_N];

ll solve(vector <int> &v) {
    int sz = v.size ();
    ll ans = 0;
    for (int l = 0; l < sz; l++) {
        map <int, int> freq;
        for (int r = l; r < sz; r++) {
            freq[v[r]]++;
            ans += freq.size();
        }
    }
    return ans;
}

ll brute_force() {
    vector <int> order(n);
    for (int i = 0; i < n; i++)
        order[i] = i + 1;
    ll ans = (1ll << 60);
    vector <int> best;
    do {
        vector <int> v;
        for (int i : order)
            v.push_back(a[i]);
        ll cnt = solve(v);
        if (ans > cnt) {
            best = v;
            ans = cnt;
        }
    } while (next_permutation(order.begin(), order.end()));
    cout << ans << "\n";
    for (int x : best)
        cout << x << " ";
    cout << "\n";
    return ans;
}

/// maybe we need to add the one with lowest freq closer to the edges
/// can we do this greedy or just by dp? greedy works!

int freq[1 + MAX_N];

ll get_div(int l, int r, int sz) {
    ll ans = 0;
    /// out out
    ans += 1ll * (l - 1) * (sz - r);
    /// in out
    ans += 1ll * (r - l + 1) * (sz - r);
    /// out in
    ans += 1ll * (r - l + 1) * (l - 1);
    /// in in
    ans += 1ll * (r - l + 1) * (r - l + 2) / 2;
 //   dbg (ans);
    return ans;
}

ll greedy_v1() {
    for (int i = 1; i <= n; i++)
        freq[a[i]]++;
    vector <int> values;
    for (int i = 1; i <= MAX_N; i++)
        if (freq[i])
            values.push_back(freq[i]);
    sort (values.begin(), values.end());
    int l = 1, r = n;
    int putL = 0, putR = 0;
    ll ans = 0;
    for (int cnt : values) {
        if (putL < putR) {
            putL += cnt;
            ans += get_div(l, l + cnt - 1, n);
            l += cnt;
        }
        else {
            putR += cnt;
            ans += get_div(r - cnt + 1, r, n);
            r -= cnt;
        }
    }
    return ans;
}

const int RADMAX = 500;

struct Query {
  int st;
  int dr;
  int ind;
};

vector <Query> q[RADMAX];

ll sol[1 + MAX_N];
int car[1 + MAX_N];
bool cmp (Query a, Query b) {
  return a.dr < b.dr;
}

int rad;

inline int bucket (int x) {
  return x / rad;
}
multiset <int> st;
void upd(int value, int val) {
    if (car[value])
        st.erase(st.find(car[value]));
    car[value] += val;
    if (car[value])
        st.insert(car[value]);
}
ll get(int L, int R){
    int putL = 0, putR = 0;
    ll ans = 0;
    int l = 1, r = R - L + 1;
    for (int cnt : st) {
        if (putL < putR) {
            putL += cnt;
            ans += get_div(l, l + cnt - 1, R - L + 1);
            l += cnt;
        }
        else {
            putR += cnt;
            ans += get_div(r - cnt + 1, r, R - L + 1);
            r -= cnt;
        }
    }
    return ans;
}
void query_mode() {
    rad = sqrt(n);
    for (int i = 1; i <= Q; i++) {
        int x, y;
        cin >> x >> y;
        q[bucket (x)].push_back ({x, y, i});
    }
    for (int b = 0; b <= rad; b++) {
        sort (q[b].begin (), q[b].end (), cmp);
        memset (car, 0, sizeof (car));
        st.clear();
        int dr = (b + 1) * rad;
        for (auto w : q[b]) {
          while (dr <= w.dr) {
            upd(a[dr], 1);
            dr++;
          }
          int bound = min (w.dr, (b + 1) * rad - 1);
          for (int i = w.st; i <= bound; i++)
            upd(a[i], 1);
          sol[w.ind] = get(w.st, w.dr);
          for (int i = w.st; i <= bound; i++)
            upd(a[i], -1);
        }
    }
    for (int i = 1; i <= Q; i++)
        cout << sol[i] << "\n";
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> Q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    query_mode();
    /*
    while (q--) {
        int l, r;
        cin >> l >> r;
    }
    ll ans_brute = brute_force();
    ll ans_greddy = greedy_v1();
    cout << ans_brute << " " << ans_greddy << "\n";*/
    return 0;
}
/**
4 2
1 1 1 1
1 2
2 4

**/

• Subtask 1: 4 / 4
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 26 / 26
• Subtask 6: 0 / 36