oj.uz

Submission #503053

# Submission time Handle Problem Language Result Execution time Memory
503053 2022-01-07T04:36:59 Z pokmui9909 Krov (COCI17_krov) C++14
84 / 140
 1500 ms 104232 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 784 KB Output is correct
2 Correct 153 ms 816 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 564 KB Output is correct
2 Correct 164 ms 872 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 928 KB Output is correct
2 Correct 264 ms 988 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 5632 KB Output is correct
2 Correct 348 ms 836 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 960 KB Output is correct
2 Correct 364 ms 1408 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 768 ms 12192 KB Output is correct
2 Correct 814 ms 1652 KB Output is correct
3 Correct 421 ms 2384 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1534 ms 9168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1583 ms 11740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1515 ms 7864 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1592 ms 104232 KB Time limit exceeded
2 Halted 0 ms 0 KB -