Submission #1085394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085394		vladilius	Meetings (IOI18_meetings)	C++17	100 / 100	3459 ms	669812 KiB

meetings

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<int, 3>
const ll inf = 1e18;

struct LCT{
    struct line{
        int k; ll b;
        ll operator ()(int x){
            return 1LL * k * x + b;
        }
    };
    vector<line> t;
    vector<ll> p;
    int n;
    LCT(int ns){
        n = ns;
        t.assign(4 * n, {0, inf});
        p.resize(4 * n);
    }
    void apply(int v, ll& x){
        t[v].b += x; p[v] += x;
    }
    void push1(int& v){
        if (!p[v]) return;
        int vv = 2 * v;
        apply(vv, p[v]);
        apply(vv + 1, p[v]);
        p[v] = 0;
    }
    void add(int v, int tl, int tr, int& l, int& r, ll& x){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            apply(v, x);
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        push1(v);
        add(vv, tl, tm, l, r, x);
        add(vv + 1, tm + 1, tr, l, r, x);
    }
    void add(int l, int r, ll x){
        if (l > r) return;
        add(1, 1, n, l, r, x);
    }
    void insert(int v, int tl, int tr, line f){
        if (tl == tr){
            if (t[v](tl) > f(tl)) t[v] = f;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        push1(v);
        if (t[v].k > f.k) swap(t[v], f);
        if (t[v](tm) > f(tm)){
            swap(t[v], f);
            insert(vv + 1, tm + 1, tr, f);
        }
        else {
            insert(vv, tl, tm, f);
        }
    }
    void chmin(int v, int tl, int tr, int& l, int& r, line& f){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            insert(v, tl, tr, f);
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        push1(v);
        chmin(vv, tl, tm, l, r, f);
        chmin(vv + 1, tm + 1, tr, l, r, f);
    }
    void chmin(int l, int r, int k, ll b){
        if (l > r) return;
        line f = {k, b};
        chmin(1, 1, n, l, r, f);
    }
    ll get(int v, int tl, int tr, int& x){
        if (tl == tr) return t[v](x);
        int tm = (tl + tr) / 2, vv = 2 * v;
        push1(v);
        if (x <= tm){
            return min(t[v](x), get(vv, tl, tm, x));
        }
        return min(t[v](x), get(vv + 1, tm + 1, tr, x));
    }
    ll get(int x){
        return get(1, 1, n, x);
    }
};

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
    int n = (int) H.size(), q = (int) L.size();
    vector<int> h(n + 1);
    for (int i = 1; i <= n; i++){
        h[i] = H[i - 1];
    }
    
    L.insert(L.begin(), 0); R.insert(R.begin(), 0);
    
    vector<int> log(n + 1);
    for (int i = 2; i <= n; i++) log[i] = log[i / 2] + 1;
    const int lg = log[n];
    vector<vector<pii>> sp(n + 1, vector<pii>(lg + 1));
    for (int i = 1; i <= n; i++) sp[i][0] = {h[i], i};
    for (int j = 1; j <= lg; j++){
        for (int i = 1; i + (1 << j) <= n + 1; i++){
            sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
        }
    }
    
    auto get = [&](int l, int r){
        int k = log[r - l + 1];
        return max(sp[l][k], sp[r - (1 << k) + 1][k]);
    };
    
    vector<int> g[n + 1], nd(n + 1);
    int cc = 0;
    
    function<int(int, int)> build1 = [&](int l, int r){
        int p = get(l, r).ss, x = -1, y = -1;
        
        if (p != l) x = build1(l, p - 1);
        if (p != r) y = build1(p + 1, r);
        
        nd[p] = ++cc;
        
        if (x != -1) g[cc].pb(x);
        if (y != -1) g[cc].pb(y);
        
        return cc;
    };
    build1(1, n);
    
    vector<vector<int>> pw(n + 1, vector<int>(lg + 1));
    vector<int> tin(n + 1), tout(n + 1);
    int timer = 0;
    function<void(int, int)> fill = [&](int v, int pr){
        tin[v] = ++timer;
        pw[v][0] = pr;
        for (int i = 1; i <= lg; i++){
            pw[v][i] = pw[pw[v][i - 1]][i - 1];
        }
        for (int i: g[v]){
            fill(i, v);
        }
        tout[v] = timer;
    };
    fill(n, n);
    
    auto check = [&](int x, int y){
        return (tin[x] <= tin[y] && tout[x] >= tout[y]);
    };
    
    auto lca = [&](int x, int y){
        if (check(x, y)) return x;
        if (check(y, x)) return y;
        for (int i = lg; i >= 0; i--){
            if (!check(pw[x][i], y)){
                x = pw[x][i];
            }
        }
        return pw[x][0];
    };
    
    vector<int> qs[n + 1];
    for (int i = 1; i <= q; i++){
        L[i]++; R[i]++;
        qs[lca(nd[L[i]], nd[R[i]])].pb(i);
    }
    
    vector<ll> out(q + 1, inf); cc = 0;
    LCT T1(n), T2(n);
    
    for (int i = 1; i <= n; i++){
        T1.add(i, i, -inf);
        T2.add(i, i, -inf);
    }
    
    function<void(int, int)> build = [&](int l, int r){
        auto [m, p] = get(l, r);
        
        if (l != p) build(l, p - 1);
        if (r != p) build(p + 1, r);
        
        for (int i: qs[++cc]){
            out[i] = min(out[i], T2.get(L[i]) + 1LL * m * (R[i] - p + 1));
            out[i] = min(out[i], T1.get(R[i]) + 1LL * m * (p - L[i] + 1));
        }
        
        // T2[i]' = min(T2[i] + m * (r - p + 1), T2[p + 1] + m * (p - i + 1)); (l <= i < p)
        T2.add(l, p, 1LL * m * (r - p + 1));
        if (r != p) T2.chmin(l, p, -m, T2.get(p + 1) + 1LL * m * (p + 1));

        // T1[i]' = min(T1[i] + m * (p - l + 1), T1[p - 1] + m * (i - p + 1)); (p < i <= r)
        T1.add(p, r, 1LL * m * (p - l + 1));
        if (l != p) T1.chmin(p, r, m, T1.get(p - 1) - 1LL * m * (p - 1));
    };
    build(1, n);
    
    
    vector<ll> ret;
    for (int i = 1; i <= q; i++) ret.pb(out[i]);
    return ret;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 40 / 40