Submission #489127

#TimeUsernameProblemLanguageResultExecution timeMemory
489127Wayne_YanDiversity (CEOI21_diversity)C++17
64 / 100
341 ms5608 KiB
#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(pair<pii,int> a, pair<pii,int> b){ if((a.ff.ff / k) == (b.ff.ff / k)) return a.ff.ss < b.ff.ss; return (a.ff.ff / k) < (b.ff.ff / k); } multiset<int> s; int times[maxN]; signed main(){ cin >> n >> q; k = n / sqrt(q); int arr[n]; F(n) cin >> arr[i]; pair<pii, int> queries[q]; F(q){ int l,r; cin >> l >> r; l--; r--; queries[i] = mp(mp(l, r), i); } sort(queries, queries + q, cmp); int fin[q]; if(q == 1){ int times[maxN] = {}; 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); }else{ int cl = 0; int cr = -1; F(q){ int nl = queries[i].ff.ff; int nr = queries[i].ff.ss; int id = queries[i].ss; // process the right bound change if(nr > cr){ while(nr > cr){ cr++; if(times[arr[cr]] != 0) s.erase(s.lower_bound(times[arr[cr]])); times[arr[cr]]++; s.insert(times[arr[cr]]); } }else if(nr < cr){ while(nr < cr){ s.erase(s.lower_bound(times[arr[cr]])); times[arr[cr]] --; if(times[arr[cr]] != 0){ s.insert(times[arr[cr]]); } cr--; } } // process the left bound change if(nl > cl){ while(nl > cl){ s.erase(s.lower_bound(times[arr[cl]])); times[arr[cl]]--; if(times[arr[cl]] != 0){ s.insert(times[arr[cl]]); } cl++; } }else if(nl < cl){ while(nl < cl){ cl--; if(times[arr[cl]] != 0){ s.erase(s.lower_bound(times[arr[cl]])); } times[arr[cl]]++; s.insert(times[arr[cl]]); } } // answer the query int ans = (cr-cl+1) * (cr-cl+2) / 2; int ldist = 0, rdist = 0; auto it = s.begin(); F((int) s.size() - 1){ if(ldist > rdist) swap(ldist, rdist); ldist += *it; ans += ((cr-cl+1) - ldist) * ldist; } fin[id] = ans; } F(q){ printf("%lld\n", fin[i]); } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...