oj.uz

Submission #605351

# Submission time Handle Problem Language Result Execution time Memory
605351 2022-07-25T16:02:28 Z yuto1115 Meetings (IOI18_meetings) C++17
100 / 100
 1818 ms 118908 KB 
#include "meetings.h"
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for (ll i = ll(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

struct line {
    ll a, b;
    
    line(ll _a, ll _b) : a(_a), b(_b) {}
    
    ll eval(ll x) { return a * x + b; }
};

class LCT {
    int n;
    vi lb, ub;
    vector<line> v;
public:
    LCT(int _n) {
        n = 1;
        while (n < _n) n *= 2;
        v.assign(2 * n, line(0, linf));
        lb.resize(2 * n);
        ub.resize(2 * n);
        rep(i, n) {
            lb[n + i] = i;
            ub[n + i] = i + 1;
        }
        for (int i = n - 1; i >= 1; --i) {
            lb[i] = lb[2 * i];
            ub[i] = ub[2 * i + 1];
        }
    }
    
    ll get_min(int p) {
        assert(0 <= p and p < n);
        ll mn = linf;
        int it = p + n;
        while (it >= 1) {
            chmin(mn, v[it].eval(p));
            it >>= 1;
        }
        return mn;
    }
    
    void add_line(int k, line now) {
        int l = lb[k], r = ub[k];
        int m = (l + r) / 2;
        bool wl = v[k].eval(l) > now.eval(l);
        bool wm = v[k].eval(m) > now.eval(m);
        bool wr = v[k].eval(r) > now.eval(r);
        if (r - l == 1) {
            if (wl) v[k] = now;
            return;
        }
        if (wl and wr) {
            v[k] = now;
            return;
        }
        if (!wl and !wr) return;
        if (wm) {
            swap(v[k], now);
            wl = !wl;
            wr = !wr;
        }
        if (wl) add_line(2 * k, now);
        else add_line(2 * k + 1, now);
    }
    
    void add_segment(int l, int r, line now) {
        assert(0 <= l and l <= r and r <= n);
        l += n, r += n;
        while (l < r) {
            if (l & 1) add_line(l++, now);
            if (r & 1) add_line(--r, now);
            l >>= 1, r >>= 1;
        }
    }
};

vl minimum_costs(vi h, vi l, vi r) {
    int n = SZ(h);
    int q = SZ(l);
    for (int &i: r) ++i;
    vl ans(q, linf);
    rep(_, 2) {
        vl v(n);
        vi st;
        vi lim(n);
        rrep(i, n) {
            vi tmp;
            while (not st.empty() and h[st.back()] < h[i]) {
                int j = st.back();
                st.pop_back();
                tmp.pb(j);
                lim[j] = i + 1;
            }
            int ub = (st.empty() ? n : st.back());
            st.pb(i);
            v[i] = ll(ub - i) * h[i];
            ll now = 0;
            tmp.pb(ub);
            rrep(j, SZ(tmp) - 1) {
                chmin(v[i], v[tmp[j]] + now + (ll) h[tmp[j]] * (tmp[j] - i - 1) + h[i]);
                now += (ll) h[tmp[j]] * (tmp[j + 1] - tmp[j]);
            }
        }
        st.clear();
        vl sum(n);
        vi ord(q);
        iota(all(ord), 0);
        sort(all(ord), [&](int i, int j) { return l[i] > l[j]; });
        int it = 0;
        vl sub(q);
        rrep(i, n) {
            while (not st.empty() and h[st.back()] < h[i]) st.pop_back();
            if (st.empty()) sum[i] = ll(n - i) * h[i];
            else {
                sum[i] = (ll) (st.back() - i) * h[i] + sum[st.back()];
                v[i] += sum[st.back()];
            }
            st.pb(i);
            while (it < q and l[ord[it]] == i) {
                auto lb = lower_bound(all(st), r[ord[it]], [&](int val, int key) { return val >= key; });
                if (lb != st.begin()) {
                    sub[ord[it]] = sum[*prev(lb)] + ll(*prev(lb) - r[ord[it]]) * h[*lb];
                } else {
                    sub[ord[it]] = (ll) (n - r[ord[it]]) * h[*lb];
                }
                chmin(ans[ord[it]], (ll) (r[ord[it]] - l[ord[it]]) * h[*lb]);
                ++it;
            }
        }
//        rep(i, n) cerr << h[i] << ' ' << v[i] << ' ' << lim[i] << ' ' << sum[i] << endl;
//        rep(i, q) cerr << sub[i] << endl;
        sort(all(ord), [&](int i, int j) { return r[i] < r[j]; });
        it = 0;
        LCT lct(n);
        st.clear();
        rep2(i, 1, n + 1) {
            while (not st.empty() and h[st.back()] <= h[i - 1]) {
                int now = st.back();
                st.pop_back();
                lct.add_segment(lim[now], now + 1, line(-h[now], (ll) h[now] * now + v[now]));
            }
            st.pb(i - 1);
            while (it < q and r[ord[it]] == i) {
                chmin(ans[ord[it]], lct.get_min(l[ord[it]]) - sub[ord[it]]);
                ++it;
            }
        }
        for (int &i: l) i = n - i;
        for (int &i: r) i = n - i;
        rep(i, q) swap(l[i], r[i]);
        reverse(all(h));
    }
    return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 504 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 6 ms 1004 KB Output is correct
11 Correct 6 ms 1004 KB Output is correct
12 Correct 8 ms 1164 KB Output is correct
13 Correct 5 ms 980 KB Output is correct
14 Correct 6 ms 1104 KB Output is correct
15 Correct 6 ms 992 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 45 ms 2644 KB Output is correct
3 Correct 150 ms 13116 KB Output is correct
4 Correct 141 ms 12732 KB Output is correct
5 Correct 124 ms 13092 KB Output is correct
6 Correct 123 ms 13196 KB Output is correct
7 Correct 157 ms 13176 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 45 ms 2644 KB Output is correct
3 Correct 150 ms 13116 KB Output is correct
4 Correct 141 ms 12732 KB Output is correct
5 Correct 124 ms 13092 KB Output is correct
6 Correct 123 ms 13196 KB Output is correct
7 Correct 157 ms 13176 KB Output is correct
8 Correct 188 ms 12768 KB Output is correct
9 Correct 114 ms 12748 KB Output is correct
10 Correct 108 ms 12740 KB Output is correct
11 Correct 136 ms 12652 KB Output is correct
12 Correct 113 ms 12724 KB Output is correct
13 Correct 115 ms 12776 KB Output is correct
14 Correct 150 ms 13164 KB Output is correct
15 Correct 139 ms 12716 KB Output is correct
16 Correct 154 ms 13096 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 6 ms 1004 KB Output is correct
11 Correct 6 ms 1004 KB Output is correct
12 Correct 8 ms 1164 KB Output is correct
13 Correct 5 ms 980 KB Output is correct
14 Correct 6 ms 1104 KB Output is correct
15 Correct 6 ms 992 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 45 ms 2644 KB Output is correct
18 Correct 150 ms 13116 KB Output is correct
19 Correct 141 ms 12732 KB Output is correct
20 Correct 124 ms 13092 KB Output is correct
21 Correct 123 ms 13196 KB Output is correct
22 Correct 157 ms 13176 KB Output is correct
23 Correct 188 ms 12768 KB Output is correct
24 Correct 114 ms 12748 KB Output is correct
25 Correct 108 ms 12740 KB Output is correct
26 Correct 136 ms 12652 KB Output is correct
27 Correct 113 ms 12724 KB Output is correct
28 Correct 115 ms 12776 KB Output is correct
29 Correct 150 ms 13164 KB Output is correct
30 Correct 139 ms 12716 KB Output is correct
31 Correct 154 ms 13096 KB Output is correct
32 Correct 1472 ms 96532 KB Output is correct
33 Correct 1111 ms 115220 KB Output is correct
34 Correct 1165 ms 115228 KB Output is correct
35 Correct 1576 ms 115236 KB Output is correct
36 Correct 1063 ms 115124 KB Output is correct
37 Correct 1138 ms 115176 KB Output is correct
38 Correct 1760 ms 118852 KB Output is correct
39 Correct 1757 ms 118908 KB Output is correct
40 Correct 1492 ms 115588 KB Output is correct
41 Correct 1673 ms 118788 KB Output is correct
42 Correct 1818 ms 118592 KB Output is correct
43 Correct 1749 ms 118740 KB Output is correct
44 Correct 1650 ms 116928 KB Output is correct