oj.uz

Submission #76204

# Submission time Handle Problem Language Result Execution time Memory
76204 2018-09-12T11:57:11 Z imeimi2000 Meetings (IOI18_meetings) C++17
100 / 100
 3463 ms 219700 KB 
#include "meetings.h"
#include <algorithm>
#include <functional>

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

int n;

const llong inf = 1e18;
vector<llong> ans;
pii seg[1 << 21];

struct query {
    int i, l, r;
    query(int i, int l, int r) : i(i), l(l), r(r) {}
};

vector<query> qs[750001];
pii arr[750001];

void init(int i, int s, int e) {
    if (s == e) {
        seg[i] = arr[s];
        return;
    }
    int m = (s + e) / 2;
    init(i << 1, s, m);
    init(i << 1 | 1, m + 1, e);
    seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}

pii getMax(int i, int s, int e, int x, int y) {
    if (e < x || y < s) return pii(0, 0);
    if (x <= s && e <= y) return seg[i];
    int m = (s + e) / 2;
    return max(getMax(i << 1, s, m, x, y), getMax(i << 1 | 1, m + 1, e, x, y));
}

struct line {
    int s, e;
    llong m, b;
    line() {}
    line(int s, int e, llong m, llong b) : s(s), e(e), m(m), b(b) {}
    llong get(int x) const {
        return m * x + b;
    }
    bool operator<=(const line &p) const {
        return get(p.s) <= p.get(p.s) && get(p.e) <= p.get(p.e);
    }
} ls[750001];

struct que {
    int s, e;
    llong add;
    que(int s, int e) : s(s), e(e), add(0) {}
    llong getRight() const {
        if (s > e) return 0;
        return ls[e].get(ls[e].e) + add;
    }
    int size() const {
        return e - s + 1;
    }
    line front() {
        line ret = ls[s];
        ret.b += add;
        return ret;
    }
    line back() {
        line ret = ls[e];
        ret.b += add;
        return ret;
    }
    void pop_front() { ++s; }
    void pop_back() { --e; }
    void push_front(line x) {
        x.b -= add;
        ls[--s] = x;
    }
    void push_back(line x) {
        x.b -= add;
        ls[++e] = x;
    }
    llong get(int x) const {
         int st = s, ed = e;
         while (st <= ed) {
            int md = (st + ed) / 2;
            if (ls[md].s <= x && x <= ls[md].e) return ls[md].get(x) + add;
            if (x < ls[md].s) ed = md - 1;
            else st = md + 1;
         }
         return 0;
    }
};

que getQuery(int s, int e) {
    if (s > e) return que(s, e);
    int m = abs(getMax(1, 1, n, s, e).second);
    que L = getQuery(s, m - 1);
    que R = getQuery(m + 1, e);
    for (query q : qs[m]) {
        ans[q.i] = min(ans[q.i], R.get(q.r) + (m - q.l + 1ll) * arr[m].first);
    }
    R.add += (m - s + 1ll) * arr[m].first;
    line l(m, m, arr[m].first, L.getRight() + (1ll - m) * arr[m].first);
    while (R.size() && l <= R.front()) {
        l.e = R.front().e;
        R.pop_front();
    }
    if (R.size()) {
        line r = R.front();
        R.pop_front();
        int st = r.s, ed = r.e;
        while (st < ed) {
            int md = (st + ed) / 2;
            if (l.get(md) < r.get(md)) st = md + 1;
            else ed = md;
        }
        l.e = st - 1;
        r.s = st;
        R.push_front(r);
    }
    R.push_front(l);
    if (L.size() < R.size()) {
        while (L.size()) {
            R.push_front(L.back());
            L.pop_back();
        }
        return R;
    }
    else {
        while (R.size()) {
            L.push_back(R.front());
            R.pop_front();
        }
        return L;
    }
}

vector<llong> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    n = H.size();
    int q = L.size();
    ans.resize(q, inf);
    
    for (int i = 0; i < n; ++i) arr[i + 1] = pii(H[i], i + 1);
    init(1, 1, n);
    for (int i = 0; i < q; ++i) {
        int mx = getMax(1, 1, n, L[i] + 1,  R[i] + 1).second;
        qs[mx].emplace_back(i, L[i] + 1, R[i] + 1);
    }
    getQuery(1, n);
    
    for (int i = 1; i <= n; ++i) qs[i].clear();
    
    for (int i = 0; i < n; ++i) arr[n - i] = pii(H[i], i - n);
    init(1, 1, n);
    for (int i = 0; i < q; ++i) {
        int mx = -getMax(1, 1, n, n - R[i], n - L[i]).second;
        qs[mx].emplace_back(i, n - R[i], n - L[i]);
    }
    getQuery(1, n);
    return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17888 KB Output is correct
2 Correct 20 ms 18108 KB Output is correct
3 Correct 20 ms 18140 KB Output is correct
4 Correct 20 ms 18080 KB Output is correct
5 Correct 19 ms 18100 KB Output is correct
6 Correct 20 ms 18300 KB Output is correct
7 Correct 20 ms 18140 KB Output is correct
8 Correct 20 ms 18448 KB Output is correct
9 Correct 19 ms 18304 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17888 KB Output is correct
2 Correct 20 ms 18108 KB Output is correct
3 Correct 20 ms 18140 KB Output is correct
4 Correct 20 ms 18080 KB Output is correct
5 Correct 19 ms 18100 KB Output is correct
6 Correct 20 ms 18300 KB Output is correct
7 Correct 20 ms 18140 KB Output is correct
8 Correct 20 ms 18448 KB Output is correct
9 Correct 19 ms 18304 KB Output is correct
10 Correct 27 ms 18680 KB Output is correct
11 Correct 26 ms 18704 KB Output is correct
12 Correct 28 ms 18668 KB Output is correct
13 Correct 27 ms 18620 KB Output is correct
14 Correct 27 ms 19072 KB Output is correct
15 Correct 27 ms 18652 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17988 KB Output is correct
2 Correct 87 ms 22200 KB Output is correct
3 Correct 297 ms 37672 KB Output is correct
4 Correct 265 ms 30452 KB Output is correct
5 Correct 271 ms 37240 KB Output is correct
6 Correct 285 ms 38652 KB Output is correct
7 Correct 293 ms 41168 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17988 KB Output is correct
2 Correct 87 ms 22200 KB Output is correct
3 Correct 297 ms 37672 KB Output is correct
4 Correct 265 ms 30452 KB Output is correct
5 Correct 271 ms 37240 KB Output is correct
6 Correct 285 ms 38652 KB Output is correct
7 Correct 293 ms 41168 KB Output is correct
8 Correct 283 ms 31308 KB Output is correct
9 Correct 222 ms 31004 KB Output is correct
10 Correct 262 ms 31256 KB Output is correct
11 Correct 271 ms 30300 KB Output is correct
12 Correct 216 ms 29924 KB Output is correct
13 Correct 254 ms 30808 KB Output is correct
14 Correct 300 ms 38020 KB Output is correct
15 Correct 250 ms 30272 KB Output is correct
16 Correct 299 ms 38092 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 17888 KB Output is correct
2 Correct 20 ms 18108 KB Output is correct
3 Correct 20 ms 18140 KB Output is correct
4 Correct 20 ms 18080 KB Output is correct
5 Correct 19 ms 18100 KB Output is correct
6 Correct 20 ms 18300 KB Output is correct
7 Correct 20 ms 18140 KB Output is correct
8 Correct 20 ms 18448 KB Output is correct
9 Correct 19 ms 18304 KB Output is correct
10 Correct 27 ms 18680 KB Output is correct
11 Correct 26 ms 18704 KB Output is correct
12 Correct 28 ms 18668 KB Output is correct
13 Correct 27 ms 18620 KB Output is correct
14 Correct 27 ms 19072 KB Output is correct
15 Correct 27 ms 18652 KB Output is correct
16 Correct 17 ms 17988 KB Output is correct
17 Correct 87 ms 22200 KB Output is correct
18 Correct 297 ms 37672 KB Output is correct
19 Correct 265 ms 30452 KB Output is correct
20 Correct 271 ms 37240 KB Output is correct
21 Correct 285 ms 38652 KB Output is correct
22 Correct 293 ms 41168 KB Output is correct
23 Correct 283 ms 31308 KB Output is correct
24 Correct 222 ms 31004 KB Output is correct
25 Correct 262 ms 31256 KB Output is correct
26 Correct 271 ms 30300 KB Output is correct
27 Correct 216 ms 29924 KB Output is correct
28 Correct 254 ms 30808 KB Output is correct
29 Correct 300 ms 38020 KB Output is correct
30 Correct 250 ms 30272 KB Output is correct
31 Correct 299 ms 38092 KB Output is correct
32 Correct 2335 ms 112248 KB Output is correct
33 Correct 1790 ms 108548 KB Output is correct
34 Correct 2319 ms 116844 KB Output is correct
35 Correct 2588 ms 114652 KB Output is correct
36 Correct 1797 ms 115544 KB Output is correct
37 Correct 2329 ms 117460 KB Output is correct
38 Correct 2847 ms 173016 KB Output is correct
39 Correct 2845 ms 173020 KB Output is correct
40 Correct 2703 ms 124096 KB Output is correct
41 Correct 2977 ms 219700 KB Output is correct
42 Correct 3463 ms 218688 KB Output is correct
43 Correct 3444 ms 218720 KB Output is correct
44 Correct 3212 ms 172660 KB Output is correct