Submission #1085227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085227		vladilius	Meetings (IOI18_meetings)	C++17	60 / 100	5529 ms	503004 KiB

meetings

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
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;
const int N = 7.5e5;

struct DS{
    struct line{
        int k; ll b;
        ll operator ()(int x){
            return 1LL * k * x + b;
        }
        line(int ks, ll bs){
            k = ks; b = bs;
        }
    };
    pair<int, ll> t[4 * N];
    pll p[4 * N];
    int n;
    DS(int ns){
        n = ns;
        for (int i = 0; i < 4 * n; i++){
            t[i] = {0, inf};
            p[i] = {0, 0};
        }
    }
    void apply(int v, pll x){
        t[v].ff += x.ff; t[v].ss += 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){
        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, pil f){
        if (tl == tr){
            if ((1LL * t[v].ff * tl + t[v].ss) > (1LL * f.ff * tl + f.ss)) t[v] = f;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        push1(v, tl, tr);
        if (t[v].ff > f.ff) swap(t[v], f);
        if ((1LL * f.ff * tm + f.ss) <= (1LL * t[v].ff * tm + t[v].ss)){
            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, pil& 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){
        pil f = {k, b};
        chmin(1, 1, n, l, r, f);
    }
    void add(int v, int tl, int tr, int& l, int& r, pil& f){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            apply(v, {f.ff, f.ss});
            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, int k, ll b){
        pil f = {k, b};
        add(1, 1, n, l, r, f);
    }
    ll get(int v, int tl, int tr, int& x){
        if (tl == tr) return (1LL * t[v].ff * x + t[v].ss);
        int tm = (tl + tr) / 2, vv = 2 * v;
        push1(v, tl, tr);
        if (x <= tm){
            return min((1LL * t[v].ff * x + t[v].ss), get(vv, tl, tm, x));
        }
        return min((1LL * t[v].ff * x + t[v].ss), 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), aa;
    for (int i = 1; i <= n; i++){
        h[i] = H[i - 1];
        aa.pb(h[i]);
    }
    
    sort(aa.begin(), aa.end());
    vector<int> vv;
    int i = 0;
    while (i < n){
        int j = i;
        while (j < n && aa[i] == aa[j]){
            j++;
        }
        vv.pb(aa[i]);
        i = j;
    }
    
    vector<int> :: iterator it;
    auto pos = [&](int x){
        it = lower_bound(vv.begin(), vv.end(), x);
        int j = (int) (it - vv.begin());
        return j;
    };
    
    vector<int> d[(int) vv.size()];
    for (int i = 1; i <= n; i++){
        d[pos(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> f;
    auto pp = [&](int x, int l, int r){
        f.clear();
        int X = pos(x);
        it = lower_bound(d[X].begin(), d[X].end(), l);
        while (it != d[X].end() && (*it) <= r){
            f.pb((*it));
            it++;
        }
    };
    
    vector<pii> all1;
    auto gp = [&](int x, int l, int r){
        pp(x, l, r);
        all1.clear();
        int pre = l;
        for (int i: f){
            if (pre < i){
                all1.pb({pre, i - 1});
            }
            pre = i + 1;
        }
        if (pre <= r) all1.pb({pre, r});
    };
    
    vector<pii> mp[(int) vv.size()];
    function<void(int, int)> build1 = [&](int l, int r){
        int m = get(l, r);
        mp[pos(m)].pb({l, r});
        
        gp(m, l, r);
        vector<pii> all = all1;
        
        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 = pos(get(l, r)), l1 = 0, r1 = (int) mp[k].size() - 1;
        while (l1 + 1 < r1){
            int m = (l1 + r1) / 2;
            if (mp[k][m].ff <= l){
                l1 = m;
            }
            else {
                r1 = m - 1;
            }
        }
        if (mp[k][r1].ff <= l) l1 = r1;
        
        qs[mp[k][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);
        
        gp(m, l, r);
        vector<pii> all = all1;
        
        for (auto [l1, r1]: all) build(l1, r1);
        
        if (all.empty()){
            T1.add(l, r, m, -1LL * m * (l - 1));
            T2.add(l, r, -m, 1LL * m * (r + 1));
        }
                
        for (auto [l1, r1]: all){
            int m1 = get(l1, r1);
            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, 0, 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, 0, 1LL * m1 * (r1 - r2));
                
                if (mn != inf) T2.chmin(l2, r2, -m1, mn + 1LL * m1 * r1);
                
                mn = min(mn, F - 1LL * m1 * (r2 - l2));
            }
            
            pp(m1, l1, r1);
            for (int i: f){
                T1.add(i, i, 0, -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, 0, mn);
            }
            reverse(f.begin(), f.end());
            for (int i: f){
                T2.add(i, i, 0, -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, 0, 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: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 0 / 40