| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 858927 |
2023-10-09T12:05:34 Z |
Ahmed57 |
Krov (COCI17_krov) |
C++17 |
|
908 ms |
56280 KB |
#include <bits/stdc++.h>
using namespace std;
int cn = 0;
#define int long long
struct lol{
long long sum[600001] = {0},cnt[600001] = {0};
void addSum(int e,int v){
while(e<=cn){
sum[e]+=v;
e+=e&-e;
}
}void addcnt(int e,int v){
while(e<=cn){
cnt[e]+=v;
e+=e&-e;
}
}long long querysum(int e){
long long res = 0;
while(e>=1){
res+=sum[e];
e-=e&-e;
}
return res;
}long long querycnt(int e){
long long res = 0;
while(e>=1){
res+=cnt[e];
e-=e&-e;
}
return res;
}
}pref,suf;
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n;
cin>>n;
long long arr[n];
for(int i = 0;i<n;i++){
cin>>arr[i];
}
long long rev[n*4+1] = {0};
map<int,int> sav;set<int> comp;
vector<int> re,dr;
for(int i = 0;i<n;i++){comp.insert(arr[i]-i);comp.insert(arr[i]+i);re.push_back(arr[i]+i);dr.push_back(arr[i]-i);dr.push_back(max(i+1,(n-i))-i);comp.insert(max(i+1,(n-i))-i);re.push_back(max(i+1,(n-i))+i);comp.insert(max(i+1,(n-i))+i);}
for(auto i:comp){
sav[i] = ++cn;
rev[cn] = i;
}
long long val[n] = {0};
for(int i = 0;i<n;i++){
suf.addSum(sav[arr[i]+i],arr[i]+i);
suf.addcnt(sav[arr[i]+i],1);
}
sort(re.begin(),re.end());
sort(dr.begin(),dr.end());
long long mi = 1e18;
for(int i = 0;i<n;i++){
suf.addSum(sav[arr[i]+i],-(arr[i]+i));
suf.addcnt(sav[arr[i]+i],-1);
pref.addSum(sav[arr[i]-i],arr[i]-i);
pref.addcnt(sav[arr[i]-i],1);
{
int ze = max(i+1,(n-i))-i;
int l = 1, r = cn , ans = 1e9;
l = sav[ze];
while(l<=r){
int mid = (l+r)/2;
int it = upper_bound(re.begin(),re.end(),rev[mid]+2*i)-re.begin()-1;
if(pref.querycnt(mid)+(it>=0?suf.querycnt(sav[re[it]]):0)>=(n+1)/2){
ans = mid;
r = mid-1;
}else l = mid+1;
}
//cout<<rev[ans]<<" "<<pref.querycnt(ans)+suf.querycnt(ans+2*i)<<endl;
long long CNT = pref.querycnt(ans) , SUM = pref.querysum(ans);
long long lo = 0;
lo+=(rev[ans])*CNT-SUM;
CNT = pref.querycnt(cn)-CNT;
SUM = pref.querysum(cn)-SUM;
lo+=SUM-rev[ans]*CNT;
//cout<<lo<<endl;
int it = lower_bound(re.begin(),re.end(),rev[ans]+2*i+1)-re.begin()-1;
int de = (it>=0?sav[re[it]]:0);
CNT = suf.querycnt(de) , SUM = suf.querysum(de);
lo+=(rev[ans]+2*i)*CNT-SUM;
CNT = suf.querycnt(cn)-CNT;
SUM = suf.querysum(cn)-SUM;
lo+=SUM-(rev[ans]+2*i)*CNT;
//cout<<lo<<endl;
mi = min(mi,lo);
}{
int ze = (max(i+1,(n-i))+i);
int l = 1, r = cn , ans = 1e9;
l = sav[ze];
//cout<<"ddd"<<endl;
while(l<=r){
int mid = (l+r)/2;
int it = upper_bound(dr.begin(),dr.end(),rev[mid]-2*i)-dr.begin()-1;
if(suf.querycnt(mid)+(it>=0?pref.querycnt(sav[dr[it]]):0)>=(n+1)/2){
ans = mid;
r = mid-1;
}else l = mid+1;
}if(ans==1e9)continue;
//cout<<"ddd"<<endl;
//cout<<rev[ans]<<" "<<pref.querycnt(ans)+suf.querycnt(ans+2*i)<<endl;
//cout<<"hh"<<endl;
//cout<<"pp"<<endl;
//cout<<ans<<endl;
long long CNT = suf.querycnt(ans) , SUM = suf.querysum(ans);
long long lo = 0;
//cout<<"pp"<<endl;
lo+=(rev[ans])*CNT-SUM;
CNT = suf.querycnt(cn)-CNT;
SUM = suf.querysum(cn)-SUM;
lo+=SUM-rev[ans]*CNT;
//cout<<"hh"<<endl;
//cout<<lo<<endl;
//cout<<"hh"<<endl;
int it = upper_bound(dr.begin(),dr.end(),rev[ans]-2*i)-dr.begin()-1;
int de = (it>=0?sav[dr[it]]:0);
CNT = pref.querycnt(de) , SUM = pref.querysum(de);
lo+=(rev[ans]-2*i)*CNT-SUM;
CNT = pref.querycnt(cn)-CNT;
SUM = pref.querysum(cn)-SUM;
lo+=SUM-(rev[ans]-2*i)*CNT;
//cout<<lo<<endl;
mi = min(mi,lo);
//cout<<"hh"<<endl;
}
}
cout<<mi<<endl;
}
/*
4 5 7 2 2
pref : 4 4 5 -1 -2
suf : 4 6 9 5 6
rev[ans]+2*i
1: 5
2 , 3 , 4 , 5 : 3
*/
Compilation message
krov.cpp: In function 'int main()':
krov.cpp:49:15: warning: unused variable 'val' [-Wunused-variable]
49 | long long val[n] = {0};
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6748 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6748 KB |
Output is correct |
| 2 |
Correct |
5 ms |
6856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7004 KB |
Output is correct |
| 2 |
Correct |
7 ms |
7004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7324 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
7516 KB |
Output is correct |
| 2 |
Correct |
11 ms |
7256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
8540 KB |
Output is correct |
| 2 |
Correct |
21 ms |
8028 KB |
Output is correct |
| 3 |
Correct |
12 ms |
7516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
178 ms |
16964 KB |
Output is correct |
| 2 |
Correct |
163 ms |
16192 KB |
Output is correct |
| 3 |
Correct |
159 ms |
17184 KB |
Output is correct |
| 4 |
Correct |
229 ms |
21424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
298 ms |
22200 KB |
Output is correct |
| 2 |
Correct |
335 ms |
25496 KB |
Output is correct |
| 3 |
Correct |
260 ms |
26588 KB |
Output is correct |
| 4 |
Correct |
220 ms |
25956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
544 ms |
28464 KB |
Output is correct |
| 2 |
Correct |
541 ms |
40772 KB |
Output is correct |
| 3 |
Correct |
264 ms |
21048 KB |
Output is correct |
| 4 |
Correct |
647 ms |
35672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
908 ms |
56280 KB |
Output is correct |
| 2 |
Correct |
732 ms |
53784 KB |
Output is correct |
| 3 |
Correct |
614 ms |
36848 KB |
Output is correct |
| 4 |
Correct |
879 ms |
45596 KB |
Output is correct |
| 5 |
Correct |
142 ms |
21396 KB |
Output is correct |
