Submission #1215157

#TimeUsernameProblemLanguageResultExecution timeMemory
1215157JuanJLDiversity (CEOI21_diversity)C++20
64 / 100
7090 ms27364 KiB
#include <bits/stdc++.h> #define fst first #define snd second #define pb push_back #define forn(i,a,b) for(int i = a; i<b; i++) #define SZ(x) (int)x.size() #define ALL(x) x.begin(),x.end() #define mset(a,v) memset(a,v,sizeof(a)) #define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; typedef long long ll; const int MAXN = 300000+4; const int MAXR = 548; int main(){FIN; ll n; cin>>n; ll q; cin>>q; vector<ll> a(n); forn(i,0,n) cin>>a[i]; forn(qq,0,q){ ll left, right; cin>>left>>right; left--; map<ll,ll> mp; forn(i,left,right) mp[a[i]]++; vector<pair<ll,ll>> ord; for(auto i:mp) ord.pb({i.snd,i.fst}); sort(ALL(ord)); pair<ll,ll> ra[MAXN]; forn(i,0,MAXN) ra[i]={-1,-1}; ll l ,r; l = left; r = right-1; forn(i,0,SZ(ord)){ if(i%2==0){ forn(j,l,l+ord[i].fst){ a[j]=ord[i].snd; } ra[ord[i].snd].fst=l; l+=ord[i].fst; ra[ord[i].snd].snd=l; }else{ for(int j = r; j>r-ord[i].fst; j--){ a[j]=ord[i].snd; } ra[ord[i].snd].snd=r+1; r-=ord[i].fst; ra[ord[i].snd].fst=r+1; } } ll res = 0; forn(i,0,MAXN){ if(ra[i].fst!=-1){ ll tam=(ra[i].snd-ra[i].fst); res+=(tam*(tam+1))/2; ll ca = 0; ca+= (ra[i].fst-left)*tam; ca+= (right-ra[i].snd)*tam; ca+= (ra[i].fst-left)*(right-ra[i].snd); res+=ca; } } cout<<res<<'\n'; } 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...