oj.uz

Submission #78672

# Submission time Handle Problem Language Result Execution time Memory
78672 2018-10-07T03:30:19 Z imeimi2000 Meetings (IOI18_meetings) C++17
100 / 100
 5392 ms 204364 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 mx[1 << 21];

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

struct line {
    llong m, b;
    llong get(int x) const {
        return m * x + b;
    }
    line() {}
    line(llong m, llong b) : m(m), b(b) {}
};

struct node {
    llong lz;
    line l;
    llong get(int x) const {
        return l.get(x);
    }
} seg[1 << 21];

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

void init(int i, int s, int e) {
    seg[i].l = line(0, inf);
    seg[i].lz = 0;
    if (s == e) {
        mx[i] = arr[s];
        return;
    }
    int m = (s + e) / 2;
    init(i << 1, s, m);
    init(i << 1 | 1, m + 1, e);
    mx[i] = max(mx[i << 1], mx[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 mx[i];
    int m = (s + e) / 2;
    return max(getMax(i << 1, s, m, x, y), getMax(i << 1 | 1, m + 1, e, x, y));
}


void update(int i, int s, int e, int x, int y, line l) {
    if (e < x || y < s) return;
    l.b -= seg[i].lz;
    int m = (s + e) / 2;
    if (x <= s && e <= y) {
        bool A = seg[i].l.get(s) < l.get(s);
        bool B = seg[i].l.get(m) < l.get(m);
        if (!B) swap(seg[i].l, l);
        if (s == e) return;
        if (A != B) update(i << 1, s, m, x, y, l);
        else update(i << 1 | 1, m + 1, e, x, y, l);
        return;
    }
    update(i << 1, s, m, x, y, l);
    update(i << 1 | 1, m + 1, e, x, y, l);
}

void add(int i, int s, int e, int x, int y, llong v) {
    if (e < x || y < s) return;
    if (x <= s && e <= y) {
        seg[i].lz += v;
        return;
    }
    int m = (s + e) / 2;
    add(i << 1, s, m, x, y, v);
    add(i << 1 | 1, m + 1, e, x, y, v);
}

llong get(int i, int s, int e, int x) {
    llong ret = seg[i].get(x);
    if (s == e) return ret + seg[i].lz;
    int m = (s + e) / 2;
    if (x <= m) return min(ret, get(i << 1, s, m, x)) + seg[i].lz;
    return min(ret, get(i << 1 | 1, m + 1, e, x)) + seg[i].lz;
}

void getQuery(int s, int e) {
    if (s > e) return;
    int m = abs(getMax(1, 1, n, s, e).second);
    getQuery(s, m - 1);
    getQuery(m + 1, e);
    for (query q : qs[m]) {
        llong R = m < q.r ? get(1, 1, n, q.r) : 0;
        ans[q.i] = min(ans[q.i], R + (m - q.l + 1ll) * arr[m].first);
    }
    add(1, 1, n, m, e, (m - s + 1ll) * arr[m].first);
    llong Lm = s < m ? get(1, 1, n, m - 1) : 0;
    line l(arr[m].first, Lm + (1ll - m) * arr[m].first);
    update(1, 1, n, m, e, 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 18 ms 17960 KB Output is correct
2 Correct 23 ms 18268 KB Output is correct
3 Correct 22 ms 18288 KB Output is correct
4 Correct 22 ms 18268 KB Output is correct
5 Correct 22 ms 18268 KB Output is correct
6 Correct 22 ms 18396 KB Output is correct
7 Correct 24 ms 18272 KB Output is correct
8 Correct 22 ms 18396 KB Output is correct
9 Correct 22 ms 18296 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17960 KB Output is correct
2 Correct 23 ms 18268 KB Output is correct
3 Correct 22 ms 18288 KB Output is correct
4 Correct 22 ms 18268 KB Output is correct
5 Correct 22 ms 18268 KB Output is correct
6 Correct 22 ms 18396 KB Output is correct
7 Correct 24 ms 18272 KB Output is correct
8 Correct 22 ms 18396 KB Output is correct
9 Correct 22 ms 18296 KB Output is correct
10 Correct 32 ms 18904 KB Output is correct
11 Correct 31 ms 18908 KB Output is correct
12 Correct 32 ms 18908 KB Output is correct
13 Correct 31 ms 18936 KB Output is correct
14 Correct 39 ms 19164 KB Output is correct
15 Correct 38 ms 18908 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17992 KB Output is correct
2 Correct 101 ms 22180 KB Output is correct
3 Correct 446 ms 38324 KB Output is correct
4 Correct 403 ms 34160 KB Output is correct
5 Correct 391 ms 37944 KB Output is correct
6 Correct 457 ms 38956 KB Output is correct
7 Correct 467 ms 40192 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17992 KB Output is correct
2 Correct 101 ms 22180 KB Output is correct
3 Correct 446 ms 38324 KB Output is correct
4 Correct 403 ms 34160 KB Output is correct
5 Correct 391 ms 37944 KB Output is correct
6 Correct 457 ms 38956 KB Output is correct
7 Correct 467 ms 40192 KB Output is correct
8 Correct 400 ms 34784 KB Output is correct
9 Correct 327 ms 34380 KB Output is correct
10 Correct 417 ms 34768 KB Output is correct
11 Correct 393 ms 34080 KB Output is correct
12 Correct 327 ms 33816 KB Output is correct
13 Correct 385 ms 34664 KB Output is correct
14 Correct 443 ms 38732 KB Output is correct
15 Correct 381 ms 34004 KB Output is correct
16 Correct 479 ms 38484 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17960 KB Output is correct
2 Correct 23 ms 18268 KB Output is correct
3 Correct 22 ms 18288 KB Output is correct
4 Correct 22 ms 18268 KB Output is correct
5 Correct 22 ms 18268 KB Output is correct
6 Correct 22 ms 18396 KB Output is correct
7 Correct 24 ms 18272 KB Output is correct
8 Correct 22 ms 18396 KB Output is correct
9 Correct 22 ms 18296 KB Output is correct
10 Correct 32 ms 18904 KB Output is correct
11 Correct 31 ms 18908 KB Output is correct
12 Correct 32 ms 18908 KB Output is correct
13 Correct 31 ms 18936 KB Output is correct
14 Correct 39 ms 19164 KB Output is correct
15 Correct 38 ms 18908 KB Output is correct
16 Correct 18 ms 17992 KB Output is correct
17 Correct 101 ms 22180 KB Output is correct
18 Correct 446 ms 38324 KB Output is correct
19 Correct 403 ms 34160 KB Output is correct
20 Correct 391 ms 37944 KB Output is correct
21 Correct 457 ms 38956 KB Output is correct
22 Correct 467 ms 40192 KB Output is correct
23 Correct 400 ms 34784 KB Output is correct
24 Correct 327 ms 34380 KB Output is correct
25 Correct 417 ms 34768 KB Output is correct
26 Correct 393 ms 34080 KB Output is correct
27 Correct 327 ms 33816 KB Output is correct
28 Correct 385 ms 34664 KB Output is correct
29 Correct 443 ms 38732 KB Output is correct
30 Correct 381 ms 34004 KB Output is correct
31 Correct 479 ms 38484 KB Output is correct
32 Correct 3550 ms 143984 KB Output is correct
33 Correct 2767 ms 140180 KB Output is correct
34 Correct 3365 ms 148560 KB Output is correct
35 Correct 3702 ms 146120 KB Output is correct
36 Correct 2755 ms 147064 KB Output is correct
37 Correct 3411 ms 149040 KB Output is correct
38 Correct 4268 ms 181160 KB Output is correct
39 Correct 4264 ms 181168 KB Output is correct
40 Correct 3997 ms 153336 KB Output is correct
41 Correct 4833 ms 204364 KB Output is correct
42 Correct 5344 ms 203400 KB Output is correct
43 Correct 5392 ms 203380 KB Output is correct
44 Correct 4757 ms 180808 KB Output is correct