Submission #1085183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085183		vladilius	Meetings (IOI18_meetings)	C++17	0 / 100	30 ms	7124 KiB

meetings

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

struct DS{
    struct line{
        ll k, b;
        ll operator ()(ll x){
            return k * x + b;
        }
        line(ll ks, ll bs){
            k = ks; b = bs;
        }
    };
    vector<line> t;
    vector<pll> p;
    int n;
    vector<ll> a;
    DS(int ns){
        n = ns;
        t.assign(4 * n, {0, inf});
        p.resize(4 * n);
    }
    void apply(int v, pll x){
        t[v].k += x.ff; t[v].b += x.ss;
        p[v].ff += x.ff; p[v].ss += x.ss;
    }
    void push1(int& v, int& tl, int& tr){
        int vv = 2 * v;
        apply(vv, p[v]); apply(vv + 1, p[v]);
        p[v] = {0, 0};
    }
    void push2(int& v, int& tl, int& tr){
        if (t[v].b == inf) return;
        int vv = 2 * v, tm = (tl + tr) / 2;
        insert(vv, tl, tm, t[v]);
        insert(vv + 1, tm + 1, tr, t[v]);
        t[v] = {0, inf};
    }
    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, tl, tr);
        if (t[v].k > f.k) swap(t[v], f);
        if (f(tm) <= t[v](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, tl, tr);
        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){
        line f(k, b);
        chmin(1, 1, n, l, r, f);
    }
    void add(int v, int tl, int tr, int& l, int& r, line& f){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            apply(v, {f.k, f.b});
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        push1(v, tl, tr);
        push2(v, tl, tr);
        add(vv, tl, tm, l, r, f);
        add(vv + 1, tm + 1, tr, l, r, f);
    }
    void add(int l, int r, ll x){
        line f(0, x);
        add(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, tl, tr);
        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){
    const int A = 1e9;

    int n = (int) H.size(), q = (int) L.size();
    vector<int> h(n + 1);
    map<int, vector<int>> d;
    for (int i = 1; i <= n; i++){
        h[i] = H[i - 1];
        d[h[i]].pb(i);
    }
    
    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<int>> pw(n + 1, vector<int>(lg + 1)), pw1(n + 1, vector<int>(lg + 1, A));
    for (int i = 1; i <= n; i++) pw[i][0] = pw1[i][0] = h[i];
    for (int j = 1; j <= lg; j++){
        for (int i = 1; i + (1 << j) <= n + 1; i++){
            pw[i][j] = max(pw[i][j - 1], pw[i + (1 << (j - 1))][j - 1]);
            pw1[i][j] = min(pw1[i][j - 1], pw1[i + (1 << (j - 1))][j - 1]);
        }
    }
    
    auto get = [&](int l, int r){
        int k = log[r - l + 1];
        return max(pw[l][k], pw[r - (1 << k) + 1][k]);
    };
    
    auto getm = [&](int l, int r){
        int k = log[r - l + 1];
        return min(pw1[l][k], pw1[r - (1 << k) + 1][k]);
    };
    
    vector<int> :: iterator it;
    auto pp = [&](int x, int l, int r){
        vector<int> f;
        it = lower_bound(d[x].begin(), d[x].end(), l);
        while (it != d[x].end() && (*it) <= r){
            f.pb((*it));
            it++;
        }
        return f;
    };
    
    auto gp = [&](int x, int l, int r){
        vector<int> f = pp(x, l, r);
        vector<pii> all;
        int pre = l;
        for (int i: f){
            if (pre < i){
                all.pb({pre, i - 1});
            }
            pre = i + 1;
        }
        if (pre <= r) all.pb({pre, r});
        return all;
    };
    
    map<int, vector<pii>> mp;
    function<void(int, int)> build1 = [&](int l, int r){
        int m = get(l, r);
        mp[m].push_back({l, r});
        
        vector<pii> all = gp(m, l, r);
        
        for (auto [l1, r1]: all){
            build1(l1, r1);
        }
    };
    build1(1, n);
    
    vector<ll> out(q + 1);
    map<pii, vector<arr3>> qs;
    for (int i = 1; i <= q; i++){
        int l, r;
        l = L[i - 1]; r = R[i - 1];
        l++; r++;
        
        if (get(l, r) == getm(l, r)){
            out[i] = 1LL * h[l] * (r - l + 1);
            continue;
        }
        int k = get(l, r), l1 = 0, r1 = (int) mp[k].size() - 1;
        vector<pii>& V = mp[k];
        while (l1 + 1 < r1){
            int m = (l1 + r1) / 2;
            if (V[m].ff <= l){
                l1 = m;
            }
            else {
                r1 = m - 1;
            }
        }
        if (V[r1].ff <= l) l1 = r1;
        
        qs[V[l1]].pb({l, r, i});
    }

    DS T1(n), T2(n);
    vector<int> :: iterator it1, it2;
    function<void(int, int)> build = [&](int l, int r){
        int m = get(l, r);
        
        vector<pii> all = gp(m, l, r);
        
        for (auto [l1, r1]: all) build(l1, r1);
        
        if (all.empty()){
            for (int i = l; i <= r; i++){
                T1.add(i, i, 1LL * m * (i - l + 1));
                T2.add(i, i, 1LL * m * (r - i + 1));
            }
        }
                
        for (auto [l1, r1]: all){
            int m1 = get(l1, r1);
            vector<pii> all1 = gp(m1, l1, r1);
            ll mn = inf;
            for (auto [l2, r2]: all1){
                // f(l1, i) = min(mn + m1 * (i - l1), f(l2, i) + m1 * (l2 - l1));
                ll F = T1.get(r2);
                T1.add(l2, r2, 1LL * m1 * (l2 - l1));

                if (mn != inf) T1.chmin(l2, r2, m1, mn - 1LL * m1 * l1);
                
                mn = min(mn, F - 1LL * m1 * (r2 - l2));
            }
            
            reverse(all1.begin(), all1.end());
            mn = inf;
            for (auto [l2, r2]: all1){
                // f(i, r1) = min(mn + m1 * (r1 - i), f(i, r2) + m1 * (r1 - r2));
                ll F = T2.get(l2);
                T2.add(l2, r2, 1LL * m1 * (r1 - r2));
                
                if (mn != inf) T2.chmin(l2, r2, -m1, mn + 1LL * m1 * r1);
                
                mn = min(mn, F - 1LL * m1 * (r2 - l2));
            }
            
            vector<int> f1 = pp(m1, l1, r1);
            for (int i: f1){
                T1.add(i, i, -T1.get(i));
                ll mn = 1LL * m1 * (i - l1 + 1);
                if (i != l1) mn = min(mn, T1.get(i - 1) + m1);
                T1.add(i, i, mn);
            }
            reverse(f1.begin(), f1.end());
            for (int i: f1){
                T2.add(i, i, -T2.get(i));
                ll mn = 1LL * m1 * (r1 - i + 1);
                if (i != r1) mn = min(mn, T2.get(i + 1) + m1);
                T2.add(i, i, mn);
            }
        }
        
        if (all.empty()) return;
        
        vector<int> x1, y1;
        for (auto [l1, r1]: all){
            x1.pb(l1); y1.pb(r1);
        }
        int N = (int) all.size(), LG = log2(N);
        vector<vector<ll>> sp(N + 1, vector<ll>(LG + 1, inf));
        for (int i = 1; i <= N; i++) sp[i][0] = (T1.get(all[i - 1].ss) - 1LL * m * (all[i - 1].ss - all[i - 1].ff));
        for (int j = 1; j <= LG; j++){
            for (int i = 1; i + (1 << j) <= N + 1; i++){
                sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
            }
        }
        
        auto gets = [&](int l, int r){
            if (l > r) return inf;
            int k = log[r - l + 1];
            return min(sp[l][k], sp[r - (1 << k) + 1][k]);
        };
        
        for (auto [ql, qr, i]: qs[{l, r}]){
            it1 = lower_bound(x1.begin(), x1.end(), ql);
            it2 = upper_bound(y1.begin(), y1.end(), qr); it2--;
            
            int i1 = (int) (it1 - x1.begin()), i2 = (int) (it2 - y1.begin());
            out[i] = gets(i1 + 1, i2 + 1);
            if (out[i] != inf) out[i] += 1LL * m * (qr - ql);
            
            if (i1 > 0){
                i1--;
                if (all[i1].ss >= ql){
                    out[i] = min(out[i], T2.get(ql) + 1LL * m * (qr - all[i1].ss));
                }
            }
            if (it2 != prev(y1.end())){
                i2++;
                if (all[i2].ff <= qr){
                    out[i] = min(out[i], T1.get(qr) + 1LL * m * (all[i2].ff - ql));
                }
            }
        }
    };
    build(1, n);
    
    vector<ll> ret;
    for (int i = 1; i <= q; i++) ret.pb(out[i]);
    return ret;
}

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