Submission #1034284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034284		vjudge1	Diversity (CEOI21_diversity)	C++17	64 / 100	7017 ms	25136 KiB

diversity

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(x) x.begin(), x.end()

const int N = 3e5;

int n, q, a[N];
map<int, int> mp[N];

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  while (q--) {
    int l, r;
    cin >> l >> r;
    l--; r--;

    auto it = mp[l].find(r);
    if (it != mp[l].end()) {
      cout << it->second << "\n";
      continue;
    }

    int sz = r-l+1;
    vector<int> vt(sz);
    for (int i = l; i <= r; i++) {
      vt[i-l] = a[i];
    }
    sort(all(vt));

    //for (int& x : vt) cerr << x << " ";
    //cerr << endl;

    vector<int> s;
    int cnt = 0;
    for (int i = 0; i < sz; i++) {
      if (i && vt[i] != vt[i-1]) {
        s.push_back(cnt);
        cnt = 1;
      }
      else cnt++;
    }
    s.push_back(cnt);

    sort(all(s));
  
    //for (int& x : s) cerr << x << " ";
    //cerr << endl;

    deque<int> dq;
    int szS = s.size();
    for (int i = 0; i < szS; i+=2) {
      dq.push_back(s[i]);
    }
    for (int i = szS - (szS % 2 ? 2 : 1); i >= 0; i-=2) {
      dq.push_back(s[i]);
    }

    //for (int& x : dq) cerr << x << " ";
    //cerr << endl;

    int ans = 0;
    int L = 1;
    while (!dq.empty()) {
      int x = dq.front() - 1; dq.pop_front();

      // sumar [L, L+x-1]
      ans += (L+x-1)*(L+x)/2 - (L-1)*(L)/2;
      L += x;

      ans += L * (sz-L+1);
      L++;
    }

    mp[l][r] = ans;
    cout <<  ans << "\n";
  }
}

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