Submission #644940

#	Time	Username	Problem	Language	Result	Execution time	Memory
644940		pakhomovee	Safety (NOI18_safety)	C++17	100 / 100	601 ms	33132 KiB

safety

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cstdio>
#include <algorithm>

using namespace std;

#define int long long

struct func {
    int k;
    int b;
    
    func(int k, int b): k(k), b(b) {}
    
    int get(int x) {
        return k * x + b;
    }
};

struct node {
    int x, y, add, sz;
    node* l = nullptr;
    node* r = nullptr;
    
    node(int x): x(x) {
        y = rand();
        add = 0;
        sz = 1;
    }
};

void push(node* v) {
    if (!v) return;
    if (v->l) {
        v->l->add += v->add;
    }
    if (v->r) {
        v->r->add += v->add;
    }
    v->x += v->add;
    v->add = 0;
}

int s(node* v) {
    if (!v) return 0;
    return v->sz;
}

void upd(node* v) {
    if (!v) return;
    v->sz = 1 + s(v->l) + s(v->r);
}

node* root = nullptr;
node* merge(node* l, node* r) {
    if (!l) return r;
    if (!r) return l;
    if (l->y > r->y) {
        push(l);
        l->r = merge(l->r, r);
        upd(l);
        return l;
    }
    push(r);
    r->l = merge(l, r->l);
    upd(r);
    return r;
}

pair<node*, node*> split(node* v, int k) {
    if (!v) return { nullptr, nullptr };
    push(v);
    if (s(v->l) + 1 <= k) {
        pair<node*, node*> q = split(v->r, k - s(v->l) - 1);
        v->r = q.first;
        upd(v);
        return { v, q.second };
    }
    pair<node*, node*> q = split(v->l, k);
    v->l = q.second;
    upd(v);
    return { q.first, v };
}

pair<node*, node*> split1(node* v, int k) {
    if (!v) return { nullptr, nullptr };
    push(v);
    if (v->x <= k) {
        pair<node*, node*> q = split1(v->r, k);
        v->r = q.first;
        upd(v);
        return { v, q.second };
    }
    pair<node*, node*> q = split1(v->l, k);
    v->l = q.second;
    upd(v);
    return { q.first, v };
}

void add(int x) {
    pair<node*, node*> q = split1(root, x);
    node* t = new node(x);
    root = merge(q.first, merge(t, q.second));
}

int back(node* v) {
    push(v);
    if (v->r) {
        return back(v->r);
    }
    return v->x;
}

void walk(node* v, vector<int> &x) {
    if (!v) return;
    push(v);
    walk(v->l, x);
    x.push_back(v->x);
    walk(v->r, x);
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, h;
    cin >> n >> h;
    vector<int> a(n);
    for (int& i : a) {
        cin >> i;
    }
    add(a[0]);
    add(a[0]);
    func f(1, -a[0]);
    for (int i = 1; i < n; ++i) {
        //  expand f->g
        int val = f.k * back(root) + f.b;
        pair<node*, node*> q = split(root, s(root) - f.k);
        if (q.first) q.first->add -= h;
        if (q.second) q.second->add += h;
        root = merge(q.first, q.second);
        f.b = val - f.k * back(root);
        //  add new function
        add(a[i]);
        add(a[i]);
        f.k += 1;
        f.b -= a[i];
    }
    int curr = f.k;
    vector<int> x;
    walk(root, x);
    auto pt = x.rbegin();
    while (curr--) {
        int x = *pt;
        int val = f.k * x + f.b;
        --f.k;
        f.b = val - f.k * x;
        ++pt;
    }
    cout << f.b;
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 29 / 29