제출 #1149955

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149955		Zero_OP	Diversity (CEOI21_diversity)	C++20	64 / 100	7057 ms	6332 KiB

diversity

#include <bits/stdc++.h>

using namespace std;

//loops (warning : long long)
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r - 1); i >= l; --i)

//pairs, tuples
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

//vectors
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sum_of(v) accumulate(all(v), 0ll)
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))

//binary search
#define lwb lower_bound
#define upb upper_bound

//other stuffs
#define dbg(x) "[" #x " = " << (x) << "]"
#define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true;
    return false;
}

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true;
    return false;
}

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using db = double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int f(const vi& a, int max_value){ //a[i] \in [0, max_value)
    int cnt = 0;
    vi check(max_value);
    FOR(i, 0, sz(a)){
        int cur = 0;
        stack<int> st;
        FOR(j, i, sz(a)){
            if(!check[a[j]]) ++cur, check[a[j]] = true, st.push(a[j]);
            cnt += cur;
        }

        while(!st.empty()){
            check[st.top()] = false;
            st.pop();
        }
    }
    return cnt;
}

int g(const vi& a){ //cnt array 
    int sum = 0;
    FOR(i, 0, sz(a)){
        int x = a[i];
        sum += x * (x + 1) / 2;
        FOR(j, i + 1, sz(a)){
            sum += x * a[j] * (j - i + 1);
        }
    }
    return sum;
}

void gen(){
    vi trick = {1, 1, 2};
    int best = 1e9;
    vector<vi> all_ok;

    do{
        int cur = g(trick);
        if(minimize(best, cur)) all_ok = {trick};
        else if(best == cur) all_ok.pb(trick);
    } while(next_permutation(all(trick)));

    cout << best << '\n';
    for(auto vec : all_ok){
        for(auto it : vec) cout << it << ' '; cout << '\n';
    }
    return;
    // // vi a = {1, 2, 1, 3, 2, 3, 1, 3, 3};
    // vi a = {3, 3, 3, 4, 4, 4, 4, 2, 2, 1};
    // vi perm(sz(a)); iota(all(perm), 0);

    // int cur = 1e9;
    // vector<vi> lst;

    // do{
    //     vi ex(sz(a));
    //     FOR(i, 0, sz(a)) ex[i] = a[perm[i]];
    //     int tmp = f(ex, 4);
    //     if(minimize(cur, tmp)){
    //         lst = {ex};
    //     } else if(cur == tmp) lst.pb(ex);
    // } while(next_permutation(all(perm)));

    // cout << cur << '\n';
    // sort(all(lst)); compact(lst);
    // cout << sz(lst) << '\n';
    // for(auto it : lst) {
    //     for(auto i : it) cout << i << ' '; cout << '\n';
    // }
}

ll calc_fast(const vi& cnt){
    ll sum_product = 0, sum = 0;
    FOR(i, 0, sz(cnt)){
        sum_product += 1LL * (i + 1) * cnt[i];
        sum += cnt[i];
    }

    // for(auto u : cnt) cout << u << ' '; cout << '\n';

    ll result = 0;
    FOR(i, 0, sz(cnt)){
        result += 1LL * cnt[i] * (cnt[i] + 1) / 2;
        sum_product -= 1LL * (i + 1) * cnt[i];
        sum -= cnt[i];
        result += 1LL * cnt[i] * (sum_product - sum * i);
    }
    return result;
}

void testcase(int ntestcase){
    int N, Q;
    cin >> N >> Q;
    vi a(N);
    FOR(i, 0, N){
        cin >> a[i];
    }

    vi b = a;
    sort(all(b)); compact(b);
    FOR(i, 0, N) a[i] = lower_bound(all(b), a[i]) - b.begin();

    FOR(_, 0, Q){
        int l, r;
        cin >> l >> r;
        --l;

        vi cnt(sz(b));
        FOR(i, l, r){
            ++cnt[a[i]];
        }

        sort(all(cnt));

        vi odd, even;
        FOR(i, 0, sz(cnt)){
            if(i & 1){
                if(cnt[i]) odd.pb(cnt[i]);
            } else{
                if(cnt[i]) even.pb(cnt[i]);
            }
        }

        reverse(all(even));
        vi result = odd;
        result.insert(result.end(), all(even));
        cout << calc_fast(result) << '\n';
    }
}  

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

#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif // LOCAL

    // gen();
    // return 0;

    int T = 1;
//    cin >> T;
    FOR(i, 0, T) testcase(i);

    return 0;
}

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