Submission #1114518

#TimeUsernameProblemLanguageResultExecution timeMemory
1114518vjudge1Diversity (CEOI21_diversity)C++17
0 / 100
1 ms336 KiB
//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 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...