Submission #503053

#	Time	Username	Problem	Language	Result	Execution time	Memory
503053		pokmui9909	Krov (COCI17_krov)	C++14	84 / 140	1592 ms	104232 KiB

krov

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
  
ll N;
ll A[100005];
ll B[100005];
ll C[100005];
const ll S = (1LL << 35);
const ll ADD = 1e9 + 7;
struct Node{
    Node *l, *r; ll v;
    Node(){
        l = r = NULL;
        v = 0;
    }
};
struct DynamicST{
    Node* root;
    DynamicST() {root = new Node();}
    void update(ll k, ll v) {update(root, 1, S, k, v);}
    ll query(ll l, ll r) {return query(root, 1, S, l, r);}
    void update(Node *node, ll s, ll e, ll k, ll v){
        if(s == e){
            node -> v += v;
            return;
        }
        ll m = (s + e) / 2;
        if(k <= m){
            if(!(node -> l)) node -> l = new Node();
            update(node -> l, s, m, k, v);
        } else {
            if(!(node -> r)) node -> r = new Node();
            update(node -> r, m + 1, e, k, v);
        }
        ll x = (node -> l ? node->l->v : 0);
        ll y = (node -> r ? node->r->v : 0);
        node -> v = x + y;
    }
    ll query(Node *node, ll s, ll e, ll l, ll r){
        if(!node) return 0;
        if(e < l || s > r) return 0;
        if(l <= s && e <= r) return node -> v;
        ll m = (s + e) / 2;
        ll x = query(node -> l, s, m, l, r);
        ll y = query(node -> r, m + 1, e, l, r);
        return x + y;
    }
};
DynamicST pfs, pfc, sfs, sfc;
  
ll f(ll X, ll K){
    ll r = 0;
    K -= X;
    r += K * pfc.query(1, K + ADD) - pfs.query(1, K + ADD);
    r += pfs.query(K + 1 + ADD, 1e10 + ADD) - K * pfc.query(K + 1 + ADD, 1e10 + ADD);
  
    K += 2 * X;
    r += K * sfc.query(1, K + ADD) - sfs.query(1, K + ADD);
    r += sfs.query(K + 1 + ADD, 1e10 + ADD) - K * sfc.query(K + 1 + ADD, 1e10 + ADD);
    return r;
}
  
int main(){
    cin.tie(0) -> sync_with_stdio(false);
  
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> A[i];
        B[i] = A[i] + i;
        C[i] = A[i] - i;
    }
    ll ans = 1e18;
    for(int i = 1; i <= N; i++){
        sfs.update(B[i] + ADD, B[i]);
        sfc.update(B[i] + ADD, 1);
    }
    for(ll i = 1; i <= N; i++){
        pfs.update(C[i] + ADD, C[i]);
        pfc.update(C[i] + ADD, 1);
        sfs.update(B[i] + ADD, -B[i]);
        sfc.update(B[i] + ADD, -1);
        ll L = 0, R = 1e12;
        while(R - L > 3){
            ll p = (L * 2 + R) / 3, q = (L + R * 2) / 3;
            f(i, p);
            if(f(i, p) <= f(i, q)) R = q;
            else L = p;
        }
        L = max(L, i);
        L = max(L, N + 1 - i);
        for(ll j = L; j <= R; j++){
            ans = min(ans, f(i, j));
        }
    }
    cout << ans;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14