| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 858910 |
2023-10-09T11:40:45 Z |
Ahmed57 |
Krov (COCI17_krov) |
C++17 |
|
773 ms |
47192 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*3+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);}
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 = 2e18;
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 , ans1 = 1e9 , ans2 = 1e9;
l = lower_bound(dr.begin(),dr.end(),ze)-dr.begin();
l = sav[dr[l]];
int L = l , R = r;
while(l<=r){
int mid = (l+r)/2;
int it = lower_bound(re.begin(),re.end(),rev[mid]+2*i+1)-re.begin()-1;
if(pref.querycnt(mid)+(it>=0?suf.querycnt(sav[re[it]]):0)>=(n+1)/2){
ans1 = mid;
r = mid-1;
}else l = mid+1;
}l = L , r = R;
while(l<=r){
int mid = (l+r)/2;
int it = lower_bound(re.begin(),re.end(),rev[mid]+2*i+1)-re.begin();
if(pref.querycnt(mid)+(it<re.size()?suf.querycnt(sav[re[it]]):0)>=(n+1)/2){
ans2 = mid;
r = mid-1;
}else l = mid+1;
}
int ans = min(ans1,ans2);
//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);
}
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:79:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | if(pref.querycnt(mid)+(it<re.size()?suf.querycnt(sav[re[it]]):0)>=(n+1)/2){
| ~~^~~~~~~~~~
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 |
6744 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7004 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7260 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
7260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
8284 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
7516 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
15820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
263 ms |
19904 KB |
Output is correct |
| 2 |
Correct |
301 ms |
21696 KB |
Output is correct |
| 3 |
Correct |
229 ms |
23900 KB |
Output is correct |
| 4 |
Correct |
193 ms |
23296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
433 ms |
24004 KB |
Output is correct |
| 2 |
Incorrect |
416 ms |
35996 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
773 ms |
47192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
