Submission #1034285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034285		vjudge1	Diversity (CEOI21_diversity)	C++17	64 / 100	7022 ms	25568 KiB

diversity

#pragma GCC optimize("O3")
#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];
unordered_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