oj.uz

Submission #858945

# Submission time Handle Problem Language Result Execution time Memory
858945 2023-10-09T12:39:37 Z Ahmed57 Krov (COCI17_krov) C++17
98 / 140
 618 ms 55856 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];
        //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};
      |               ^~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7000 KB Output is correct
2 Correct 4 ms 7004 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 4 ms 7004 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7000 KB Output is correct
2 Correct 5 ms 7004 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 7516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7540 KB Output is correct
2 Correct 8 ms 7256 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 8540 KB Output is correct
2 Correct 15 ms 8076 KB Output is correct
3 Correct 8 ms 7516 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 16972 KB Output is correct
2 Correct 104 ms 16296 KB Output is correct
3 Correct 105 ms 17184 KB Output is correct
4 Correct 148 ms 21084 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 22032 KB Output is correct
2 Correct 216 ms 25508 KB Output is correct
3 Correct 171 ms 26428 KB Output is correct
4 Incorrect 141 ms 25804 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 28460 KB Output is correct
2 Correct 341 ms 41264 KB Output is correct
3 Correct 162 ms 21044 KB Output is correct
4 Correct 398 ms 35376 KB Output is correct

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 55856 KB Output is correct
2 Incorrect 493 ms 53024 KB Output isn't correct
3 Halted 0 ms 0 KB -