oj.uz

Submission #1085176

# Submission time Handle Problem Language Result Execution time Memory
1085176 2024-09-07T16:37:29 Z vladilius Meetings (IOI18_meetings) C++17
60 / 100
 5500 ms 590980 KB 
#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){
        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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 30 ms 2396 KB Output is correct
3 Correct 29 ms 2396 KB Output is correct
4 Correct 30 ms 2396 KB Output is correct
5 Correct 30 ms 2396 KB Output is correct
6 Correct 14 ms 2172 KB Output is correct
7 Correct 30 ms 2392 KB Output is correct
8 Correct 13 ms 1624 KB Output is correct
9 Correct 19 ms 1628 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 30 ms 2396 KB Output is correct
3 Correct 29 ms 2396 KB Output is correct
4 Correct 30 ms 2396 KB Output is correct
5 Correct 30 ms 2396 KB Output is correct
6 Correct 14 ms 2172 KB Output is correct
7 Correct 30 ms 2392 KB Output is correct
8 Correct 13 ms 1624 KB Output is correct
9 Correct 19 ms 1628 KB Output is correct
10 Correct 62 ms 4176 KB Output is correct
11 Correct 57 ms 4184 KB Output is correct
12 Correct 56 ms 4212 KB Output is correct
13 Correct 58 ms 4176 KB Output is correct
14 Correct 26 ms 3676 KB Output is correct
15 Correct 55 ms 3200 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 60 ms 7136 KB Output is correct
3 Correct 833 ms 57436 KB Output is correct
4 Correct 1661 ms 54848 KB Output is correct
5 Correct 898 ms 56260 KB Output is correct
6 Correct 757 ms 53804 KB Output is correct
7 Correct 810 ms 54164 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 60 ms 7136 KB Output is correct
3 Correct 833 ms 57436 KB Output is correct
4 Correct 1661 ms 54848 KB Output is correct
5 Correct 898 ms 56260 KB Output is correct
6 Correct 757 ms 53804 KB Output is correct
7 Correct 810 ms 54164 KB Output is correct
8 Correct 1718 ms 59900 KB Output is correct
9 Correct 1699 ms 60068 KB Output is correct
10 Correct 1714 ms 59872 KB Output is correct
11 Correct 1852 ms 60016 KB Output is correct
12 Correct 1885 ms 59840 KB Output is correct
13 Correct 1968 ms 59900 KB Output is correct
14 Correct 901 ms 62888 KB Output is correct
15 Correct 1958 ms 59784 KB Output is correct
16 Correct 1101 ms 55064 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 30 ms 2396 KB Output is correct
3 Correct 29 ms 2396 KB Output is correct
4 Correct 30 ms 2396 KB Output is correct
5 Correct 30 ms 2396 KB Output is correct
6 Correct 14 ms 2172 KB Output is correct
7 Correct 30 ms 2392 KB Output is correct
8 Correct 13 ms 1624 KB Output is correct
9 Correct 19 ms 1628 KB Output is correct
10 Correct 62 ms 4176 KB Output is correct
11 Correct 57 ms 4184 KB Output is correct
12 Correct 56 ms 4212 KB Output is correct
13 Correct 58 ms 4176 KB Output is correct
14 Correct 26 ms 3676 KB Output is correct
15 Correct 55 ms 3200 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 60 ms 7136 KB Output is correct
18 Correct 833 ms 57436 KB Output is correct
19 Correct 1661 ms 54848 KB Output is correct
20 Correct 898 ms 56260 KB Output is correct
21 Correct 757 ms 53804 KB Output is correct
22 Correct 810 ms 54164 KB Output is correct
23 Correct 1718 ms 59900 KB Output is correct
24 Correct 1699 ms 60068 KB Output is correct
25 Correct 1714 ms 59872 KB Output is correct
26 Correct 1852 ms 60016 KB Output is correct
27 Correct 1885 ms 59840 KB Output is correct
28 Correct 1968 ms 59900 KB Output is correct
29 Correct 901 ms 62888 KB Output is correct
30 Correct 1958 ms 59784 KB Output is correct
31 Correct 1101 ms 55064 KB Output is correct
32 Execution timed out 5595 ms 590980 KB Time limit exceeded
33 Halted 0 ms 0 KB -