Submission #1087339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087339		MercubytheFirst	Diversity (CEOI21_diversity)	C++17	0 / 100	47 ms	4956 KiB

diversity

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define endl '\n'

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 37
#endif

ll n, Q;
ll cost(ll l, ll m) {
    const ll r = l + m - 1;
    return l*(n - l) + (n*m) - (r - l + 1)*(r + l)/2;
}

inline void solve(){
    const ll N = 3e5 + 37;
    cin >> n >> Q;
    assert(Q == 1);
    vector<ll> v(n);
    vector<pair<ll, ll> > keep(N);
    for(ll i = 0; i < N; ++i) {
        keep[i].second = i;
    }
    for(ll& i : v) {
        cin >> i;
        keep[i].first++;
    }
    sort(keep.begin(), keep.end());
    ll ans = 0;
    set<array<ll, 3> > pos{{0, 0, 0}, {0, n - 1, 1}};
    for(auto& p : keep) {
        if(p.first == 0) {
            continue;
        }
        assert(!pos.empty());
        auto cur = *pos.begin();
        pos.erase(pos.begin());
        const ll l = (cur[2] ? cur[1] - p.first + 1 : cur[1]), m = p.first;
        debug(p, l, cost(l, m));
        ans += cost(l, m);
        auto dup = cur;
        dup[2] ^= 1;
        dup[1] = cur[1] + ((m - 1) * (cur[2] ? -1 : 1));
        debug(cur, dup);
        if(pos.count({cur[0], m*(cur[2] ? -1 : 1) + cur[1], cur[2] ^ 1})) {
            pos.erase({cur[0], m*(cur[2] ? -1 : 1) + cur[1], cur[2] ^ 1});
        }
        if(cur[2] == 0 and l + m < n) {
            ll idx = l + m;
            pos.insert({idx, idx, 0});
        }
        else if(cur[2] == 1 and l > 0) {
            pos.insert({l - 1, n - (l - 1) - 1, 1});
        }
    }
    cout << ans << endl;
}

 
signed main(){
    #ifdef LOCAL
    freopen("test.in", "r", stdin);
    freopen("err.txt", "w", stderr);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); 
    // signed t; cin >> t; while(t--)
        solve();
}

Compilation message (stderr)

diversity.cpp: In function 'void solve()':
diversity.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 37
      |                    ^~
diversity.cpp:42:9: note: in expansion of macro 'debug'
   42 |         debug(p, l, cost(l, m));
      |         ^~~~~
diversity.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 37
      |                    ^~
diversity.cpp:47:9: note: in expansion of macro 'debug'
   47 |         debug(cur, dup);
      |         ^~~~~

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