This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e18;
const int N = 2e5+50,Q = 2e5+50;
void solve() {
int n,q;
cin >> n >> q;
vi a(n+1);
for (int i=1;i<=n;i++) cin >> a[i];
while (q--) {
int L,R;
cin >> L >> R;
n = R-L+1;
map<int,int> mp;
for (int j = L;j<=R;j++) mp[a[j]]++;
vi ps;
for (auto it : mp) ps.push_back(it.ss);
sort(ps.begin(),ps.end());
deque<int> dq;
int a = ps.back()/2;
int b = ps.back()-a;
dq.push_back(ps.back());
ps.pop_back();
int l = n/2-a+1;
int r = n/2+1+b-1;
while (!ps.empty()) {
if (n/2-l+1 <= r-n/2-1) l-=ps.back(),dq.push_front(ps.back());
else r+=ps.back(),dq.push_back(ps.back());
ps.pop_back();
}
int ans = 0;
int cur = 1;
for (auto it : dq) {
int r = cur+it-1;
ans+=n*(n+1)/2-cur*(cur-1)/2-(n-r)*(n-r+1)/2;
cur = r+1;
}
cout << ans << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Dodi
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |