Submission #639873

#TimeUsernameProblemLanguageResultExecution timeMemory
639873pliamDiversity (CEOI21_diversity)C++17
0 / 100
1 ms212 KiB
#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 (stderr)

diversity.cpp: In function 'int main()':
diversity.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d%d",&N,&Q);
      |     ~~~~~^~~~~~~~~~~~~~
diversity.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         scanf("%d",&a[i+1]);
      |         ~~~~~^~~~~~~~~~~~~~
diversity.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%d%d",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~
#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...