oj.uz

Submission #1085285

# Submission time Handle Problem Language Result Execution time Memory
1085285 2024-09-07T20:41:29 Z vladilius Meetings (IOI18_meetings) C++17
60 / 100
 4672 ms 786432 KB 
#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{
        ll k, b;
        ll operator ()(ll x){
            return k * x + b;
        }
        line(ll ks, ll bs){
            k = ks; b = bs;
        }
    };
    vector<line> t;
    vector<pil> p;
    int n;
    DS(int ns){
        n = ns;
        t.assign(4 * n, {0, inf});
        p.resize(4 * n);
    }
    void apply(int v, pil 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 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);
        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){
        line f(k, b);
        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), 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]);
    };
    
    int f[n + 1], fs = 0;
    auto pp = [&](int x, int l, int r){
        fs = 0;
        int X = pos(x);
        it = lower_bound(d[X].begin(), d[X].end(), l);
        while (it != d[X].end() && (*it) <= r){
            f[fs++] = (*it);
            it++;
        }
    };
    
    pii all1[n + 1]; int s1 = 0;
    auto gp = [&](int x, int l, int r){
        pp(x, l, r);
        s1 = 0;
        int pre = l;
        for (int j = 0; j < fs; j++){
            int i = f[j];
            if (pre < i){
                all1[s1++] = {pre, i - 1};
            }
            pre = i + 1;
        }
        if (pre <= r) all1[s1++] = {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(s1);
        for (int i = 0; i < s1; i++) all[i] = all1[i];
        
        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);
    for (int i = 1; i <= n; i++){
        T1.add(i, i, 0, -inf);
        T2.add(i, i, 0, -inf);
    }
    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(s1);
        for (int i = 0; i < s1; i++) all[i] = all1[i];
        
        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 (int i = 0; i < s1; i++){
                // f(l1, i) = min(mn + m1 * (i - l1), f(l2, i) + m1 * (l2 - l1));
                auto [l2, r2] = all1[i];
                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));
            }
            
            mn = inf;
            for (int i = s1 - 1; i >= 0; i--){
                // f(i, r1) = min(mn + m1 * (r1 - i), f(i, r2) + m1 * (r1 - r2));
                auto [l2, r2] = all1[i];
                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));
            }
            
            for (int j = 0; j < fs; j++){
                int i = f[j];
                ll mn = 1LL * m1 * (i - l1 + 1);
                if (i > l1) mn = min(mn, T1.get(i - 1) + m1);
                T1.add(i, i, 0, mn - T1.get(i));
            }
            for (int j = fs - 1; j >= 0; j--){
                int i = f[j];
                ll mn = 1LL * m1 * (r1 - i + 1);
                if (i < r1) mn = min(mn, T2.get(i + 1) + m1);
                T2.add(i, i, 0, mn - T2.get(i));
            }
        }
        
        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 (i2 + 1 < all.size()){
                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;
}

Compilation message

meetings.cpp: In lambda function:
meetings.cpp:324:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  324 |             if (i2 + 1 < all.size()){
      |                 ~~~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 9 ms 2216 KB Output is correct
3 Correct 13 ms 2504 KB Output is correct
4 Correct 8 ms 2248 KB Output is correct
5 Correct 9 ms 2136 KB Output is correct
6 Correct 4 ms 2136 KB Output is correct
7 Correct 8 ms 2208 KB Output is correct
8 Correct 3 ms 1628 KB Output is correct
9 Correct 5 ms 1628 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 9 ms 2216 KB Output is correct
3 Correct 13 ms 2504 KB Output is correct
4 Correct 8 ms 2248 KB Output is correct
5 Correct 9 ms 2136 KB Output is correct
6 Correct 4 ms 2136 KB Output is correct
7 Correct 8 ms 2208 KB Output is correct
8 Correct 3 ms 1628 KB Output is correct
9 Correct 5 ms 1628 KB Output is correct
10 Correct 16 ms 3932 KB Output is correct
11 Correct 16 ms 3932 KB Output is correct
12 Correct 18 ms 3784 KB Output is correct
13 Correct 18 ms 3932 KB Output is correct
14 Correct 9 ms 3676 KB Output is correct
15 Correct 23 ms 3420 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 30 ms 7324 KB Output is correct
3 Correct 228 ms 58964 KB Output is correct
4 Correct 222 ms 56512 KB Output is correct
5 Correct 145 ms 58004 KB Output is correct
6 Correct 133 ms 55120 KB Output is correct
7 Correct 162 ms 55876 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 30 ms 7324 KB Output is correct
3 Correct 228 ms 58964 KB Output is correct
4 Correct 222 ms 56512 KB Output is correct
5 Correct 145 ms 58004 KB Output is correct
6 Correct 133 ms 55120 KB Output is correct
7 Correct 162 ms 55876 KB Output is correct
8 Correct 349 ms 61620 KB Output is correct
9 Correct 307 ms 61556 KB Output is correct
10 Correct 376 ms 61596 KB Output is correct
11 Correct 355 ms 61508 KB Output is correct
12 Correct 320 ms 61508 KB Output is correct
13 Correct 422 ms 61504 KB Output is correct
14 Correct 181 ms 64492 KB Output is correct
15 Correct 374 ms 61256 KB Output is correct
16 Correct 185 ms 56740 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 9 ms 2216 KB Output is correct
3 Correct 13 ms 2504 KB Output is correct
4 Correct 8 ms 2248 KB Output is correct
5 Correct 9 ms 2136 KB Output is correct
6 Correct 4 ms 2136 KB Output is correct
7 Correct 8 ms 2208 KB Output is correct
8 Correct 3 ms 1628 KB Output is correct
9 Correct 5 ms 1628 KB Output is correct
10 Correct 16 ms 3932 KB Output is correct
11 Correct 16 ms 3932 KB Output is correct
12 Correct 18 ms 3784 KB Output is correct
13 Correct 18 ms 3932 KB Output is correct
14 Correct 9 ms 3676 KB Output is correct
15 Correct 23 ms 3420 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 30 ms 7324 KB Output is correct
18 Correct 228 ms 58964 KB Output is correct
19 Correct 222 ms 56512 KB Output is correct
20 Correct 145 ms 58004 KB Output is correct
21 Correct 133 ms 55120 KB Output is correct
22 Correct 162 ms 55876 KB Output is correct
23 Correct 349 ms 61620 KB Output is correct
24 Correct 307 ms 61556 KB Output is correct
25 Correct 376 ms 61596 KB Output is correct
26 Correct 355 ms 61508 KB Output is correct
27 Correct 320 ms 61508 KB Output is correct
28 Correct 422 ms 61504 KB Output is correct
29 Correct 181 ms 64492 KB Output is correct
30 Correct 374 ms 61256 KB Output is correct
31 Correct 185 ms 56740 KB Output is correct
32 Correct 4657 ms 563944 KB Output is correct
33 Correct 3991 ms 569804 KB Output is correct
34 Correct 4374 ms 569808 KB Output is correct
35 Correct 4672 ms 570024 KB Output is correct
36 Correct 4019 ms 570328 KB Output is correct
37 Correct 4629 ms 571372 KB Output is correct
38 Correct 2422 ms 550960 KB Output is correct
39 Correct 1926 ms 550748 KB Output is correct
40 Correct 3918 ms 600516 KB Output is correct
41 Runtime error 2318 ms 786432 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -