제출 #805654

#제출 시각아이디문제언어결과실행 시간메모리
805654MohamedAhmed04Izbori (COCI22_izbori)C++14
40 / 110
3069 ms30652 KiB
#include <bits/stdc++.h> using namespace std ; const int MAX = 1e6 + 10 ; const int B = 1 ; int arr[MAX] ; int n ; vector<int>occ[MAX] ; void compress() { vector<int>v ; for(int i = 1 ; i <= n ; ++i) v.push_back(arr[i]) ; sort(v.begin() , v.end()) ; v.erase(unique(v.begin() , v.end()) , v.end()) ; for(int i = 1 ; i <= n ; ++i) { arr[i] = lower_bound(v.begin() , v.end() , arr[i]) - v.begin() ; arr[i]++ ; } } int freq[MAX] ; long long solve_big(int x) { for(int i = 0 ; i <= 3*n ; ++i) freq[i] = 0 ; int idx = n-1 , cur = n ; long long ans = 0 , cnt = 0 ; freq[n]++ , cnt = 0 ; for(int i = 1 ; i <= n ; ++i) { if(arr[i] == x) idx++ , cnt += freq[idx] , ++cur ; else cnt -= freq[idx] , --idx , --cur ; ans += cnt ; freq[cur]++ ; if(cur <= idx) cnt++ ; } return ans ; } long long calc(int l , int r) { return (1ll * r * (r+1ll) / 2ll - 1ll * (l-1) * (l) / 2ll) ; } long long solve_small(int x) { long long ans = 0 ; int sz = occ[x].size() ; for(int i = 0 ; i < sz ; ++i) { for(int j = 0 ; j <= i ; ++j) { int cnt = i-j+1 - (occ[x][i] - occ[x][j] + 1 - (i-j+1)) - 1 ; int a = occ[x][j] , b = n+1 - occ[x][i] ; if(j > 0) a -= occ[x][j-1] ; if(i+1 < sz) b = occ[x][i+1] - occ[x][i] ; if(x < 0) continue ; // start at occ[x][j] ans += min(cnt+1 , b) , --a ; // end at occ[x][i] ans += min(cnt , a) , --b ; // start < oxx[x][j] and end > oxx[j][i] int y = max(0 , min(cnt-a , b)) ; ans += 1ll * a * y ; b -= y , cnt -= y ; ans += calc(cnt - min(cnt , b) , cnt-1) ; } } return ans ; } int main() { ios_base::sync_with_stdio(0) ; cin.tie(0) ; cin>>n ; for(int i = 1 ; i <= n ; ++i) cin>>arr[i] ; compress() ; for(int i = 1 ; i <= n ; ++i) occ[arr[i]].push_back(i) ; long long ans = 0 ; for(int i = 1 ; i <= n ; ++i) { if(occ[i].size() >= B) ans += solve_big(i) ; else ans += solve_small(i) ; } return cout<<ans<<"\n" , 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...