# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
639873 | 2022-09-12T14:44:50 Z | pliam | Diversity (CEOI21_diversity) | C++17 | 1 ms | 212 KB |
#include <bits/stdc++.h> using namespace std; #define MAXN 300005 typedef long long ll; int N,Q; int a[MAXN]; vector<pair<int,int>> queries; int main(){ scanf("%d%d",&N,&Q); for(int i=0;i<N;i++){ scanf("%d",&a[i+1]); } for(int i=0;i<Q;i++){ int l,r; scanf("%d%d",&l,&r); queries.push_back({l,r}); } for(auto q:queries){ ll l,r; tie(l,r)=q; ll m=r-l+1; vector<int> items; map<int,pair<ll,ll>> spec_pos; for(int i=l;i<=r;i++){ items.push_back(a[i]); } sort(items.begin(),items.end()); for(int i=0;i<m;i++){ int spec=items[i]; if(!spec_pos.count(spec)){ spec_pos[spec]={i,i}; }else{ spec_pos[spec].second=i; } } ll ans=0; for(auto p:spec_pos){ //p.second are the positions ll locans=(m*(m+1))/2; //now subtract those that do not contain it ll rangel=p.second.first; ll ranger=m-1-p.second.second; locans-=(rangel*(rangel+1))/2+(ranger*(ranger+1))/2; ans+=locans; } printf("%lld\n",ans); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Incorrect | 1 ms | 212 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 212 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 212 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 212 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Incorrect | 1 ms | 212 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Incorrect | 1 ms | 212 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |