Submission #489116

#	Time	Username	Problem	Language	Result	Execution time	Memory
489116		Wayne_Yan	Diversity (CEOI21_diversity)	C++17	64 / 100	111 ms	6860 KiB

diversity

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
typedef int64_t ll;
typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)>>1)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)
#define debug(x) (cerr << (#x) << " = " << x << "\n")
template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

int n,q,k;
const int maxN = 3e5+10;

bool cmp(pii a, pii b){
  if((a.ff / k) == (b.ff / k)) return a.ss < b.ss;
  return (a.ff / k) < (b.ff / k);
}

int times[maxN];
signed main(){
  cin >> n >> q;
  k = n / sqrt(q);


  int arr[n];
  F(n) cin >> arr[i];
  pii queries[q];
  F(q){
    int l,r;
    cin >> l >> r;
    l--; r--;
    queries[i] = mp(l, r);
  }
  sort(queries, queries + q, cmp);
  
  if(q == 1){
    F(n) times[arr[i]]++;
    sort(times, times+maxN);
    int ans = (n * (n+1)) / 2;
    int ldist = 0;
    int rdist = 0;
    F(maxN - 1){
      if(times[i] == 0) continue;
      if(ldist > rdist) swap(ldist, rdist);
      ldist += times[i];
      ans += (n - ldist) * ldist;
      
    }
    printf("%lld\n", ans);
  }



  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