제출 #618191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
618191		Joshc	Diversity (CEOI21_diversity)	C++11	64 / 100	7081 ms	4484 KiB

diversity

#include <bits/stdc++.h>
using namespace std;

#define ll long long

int cnt[300005], a[300005], l[300005], r[300005];
ll n, out[50005];
const int SQRT = 900;

ll f(ll a, ll b, ll x) {
    // sum((a+bi) choose 2) with x terms
    return x*a*a + a*b*x*(x-1) + x*(x-1)*(2*x-1)/6*b*b - (2*a+b*(x-1))*x/2;
}

ll val(ll start, ll sz, ll num) {
    // We have num blocks of size sz, starting at position start
    // What is the total contribution?
    if (!num || !sz) return 0;
    ll res = n*(n+1)*num;
    res -= f(start, sz, num);
    res -= f(n-(start+sz*num-1)+1, sz, num);
    return res/2;
}

bool comp(int x, int y) {
    int p = l[x]/SQRT, q = l[y]/SQRT;
    if (p != q) return p < q;
    return p&1 ? (r[x] < r[y]) : (r[x] > r[y]);
}

map<int, int> v;
int freq[300005];

void add(int x) {
    if (freq[x] && !--v[freq[x]]) v.erase(freq[x]);
    v[++freq[x]]++;
}

void remove(int x) {
    if (!--v[freq[x]]) v.erase(freq[x]);
    v[--freq[x]]++;
}

ll solve() {
    ll ans = 0;
    int lsum = 0, rsum = 0;
    for (auto p : v) {
        int sz = p.first;
        int num = p.second;
        int lv = 0, rv = 0;
        if (lsum < rsum) {
            lv = num-num/2;
            rv = num/2;
        } else {
            rv = num-num/2;
            lv = num/2;
        }
        ans += val(lsum+1, sz, lv) + val(rsum+1, sz, rv);
        lsum += sz*lv;
        rsum += sz*rv;
    }
    return ans;
}

int main() {
    int q, x;
    scanf("%lld%d", &n, &q);
    vector<int> order;
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    for (int i=1; i<=q; i++) {
        scanf("%d%d", &l[i], &r[i]);
        order.push_back(i);
    }
    sort(order.begin(), order.end(), comp);
    
    int L = 1, R = 0;

    for (int i : order) {
        while (R < r[i]) add(a[++R]);
        while (L > l[i]) add(a[--L]);
        while (R > r[i]) remove(a[R--]);
        while (L < l[i]) remove(a[L++]);
        n = R-L+1;
        out[i] = solve();
    }

    for (int i=1; i<=q; i++) printf("%lld\n", out[i]);
}

컴파일 시 표준 에러 (stderr) 메시지

diversity.cpp: In function 'int main()':
diversity.cpp:66:12: warning: unused variable 'x' [-Wunused-variable]
   66 |     int q, x;
      |            ^
diversity.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%lld%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
diversity.cpp:69:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     for (int i=1; i<=n; i++) scanf("%d", &a[i]);
      |                              ~~~~~^~~~~~~~~~~~~
diversity.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d%d", &l[i], &r[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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