oj.uz

Submission #78673

# Submission time Handle Problem Language Result Execution time Memory
78673 2018-10-07T04:03:36 Z imeimi2000 Meetings (IOI18_meetings) C++17
60 / 100
 3022 ms 241900 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 arr[750001][20];
int l2[750001];

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];

void init() {
    for (int i = 1; i < 20; ++i) {
        for (int j = 1; j <= n; ++j) {
            int k = j + (1 << (i - 1));
            arr[j][i] = arr[j][i - 1];
            if (k <= n) arr[j][i] = max(arr[j][i], arr[k][i - 1]);
        }
    }
}

pii getMax(int x, int y) {
    int p = l2[y - x + 1];
    return max(arr[x][p], arr[y - (1 << p) + 1][p]);
}

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

void updateS(int i, int s, int e, int x, int y, line l) {
    if (e < x || y < s) return;
    if (x <= s && e <= y) {
        updateL(i, s, e, l);
        return;
    }
    l.b -= seg[i].lz;
    int m = (s + e) / 2;
    updateS(i << 1, s, m, x, y, l);
    updateS(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, v;
    tie(v, m) = getMax(s, e);
    if (m < 0) m = -m;
    
    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) * v);
    }
    add(1, 1, n, m, e, (m - s + 1ll) * v);
    llong Lm = s < m ? get(1, 1, n, m - 1) : 0;
    line l(v, Lm + (1ll - m) * v);
    updateS(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 = 1, j = 0; i <= n; ++i) {
        if ((1 << (j + 1)) < i) ++j;
        l2[i] = j;
    }
    
    for (int i = 0; i < n; ++i) arr[i + 1][0] = pii(H[i], i + 1);
    init();
    for (int i = 0; i <= 750000; ++i) seg[i].l = line(0, inf), seg[i].lz = 0;
    for (int i = 0; i < q; ++i) {
        int mx = getMax(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][0] = pii(H[i], i - n);
    init();
    for (int i = 0; i <= 750000; ++i) seg[i].l = line(0, inf), seg[i].lz = 0;
    for (int i = 0; i < q; ++i) {
        int mx = -getMax(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 37 ms 35536 KB Output is correct
2 Correct 40 ms 36088 KB Output is correct
3 Correct 40 ms 36100 KB Output is correct
4 Correct 40 ms 36108 KB Output is correct
5 Correct 40 ms 36028 KB Output is correct
6 Correct 40 ms 36208 KB Output is correct
7 Correct 40 ms 36136 KB Output is correct
8 Correct 40 ms 36192 KB Output is correct
9 Correct 40 ms 36168 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 35536 KB Output is correct
2 Correct 40 ms 36088 KB Output is correct
3 Correct 40 ms 36100 KB Output is correct
4 Correct 40 ms 36108 KB Output is correct
5 Correct 40 ms 36028 KB Output is correct
6 Correct 40 ms 36208 KB Output is correct
7 Correct 40 ms 36136 KB Output is correct
8 Correct 40 ms 36192 KB Output is correct
9 Correct 40 ms 36168 KB Output is correct
10 Correct 49 ms 36860 KB Output is correct
11 Correct 48 ms 36856 KB Output is correct
12 Correct 48 ms 36780 KB Output is correct
13 Correct 47 ms 36828 KB Output is correct
14 Correct 49 ms 37000 KB Output is correct
15 Correct 49 ms 36856 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 35548 KB Output is correct
2 Correct 95 ms 40400 KB Output is correct
3 Correct 393 ms 63020 KB Output is correct
4 Correct 323 ms 58852 KB Output is correct
5 Correct 364 ms 62616 KB Output is correct
6 Correct 386 ms 63708 KB Output is correct
7 Correct 402 ms 64920 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 35548 KB Output is correct
2 Correct 95 ms 40400 KB Output is correct
3 Correct 393 ms 63020 KB Output is correct
4 Correct 323 ms 58852 KB Output is correct
5 Correct 364 ms 62616 KB Output is correct
6 Correct 386 ms 63708 KB Output is correct
7 Correct 402 ms 64920 KB Output is correct
8 Correct 400 ms 59440 KB Output is correct
9 Correct 271 ms 59068 KB Output is correct
10 Correct 338 ms 59484 KB Output is correct
11 Correct 332 ms 58808 KB Output is correct
12 Correct 270 ms 58420 KB Output is correct
13 Correct 317 ms 59256 KB Output is correct
14 Correct 381 ms 63392 KB Output is correct
15 Correct 319 ms 58756 KB Output is correct
16 Correct 382 ms 63208 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 35536 KB Output is correct
2 Correct 40 ms 36088 KB Output is correct
3 Correct 40 ms 36100 KB Output is correct
4 Correct 40 ms 36108 KB Output is correct
5 Correct 40 ms 36028 KB Output is correct
6 Correct 40 ms 36208 KB Output is correct
7 Correct 40 ms 36136 KB Output is correct
8 Correct 40 ms 36192 KB Output is correct
9 Correct 40 ms 36168 KB Output is correct
10 Correct 49 ms 36860 KB Output is correct
11 Correct 48 ms 36856 KB Output is correct
12 Correct 48 ms 36780 KB Output is correct
13 Correct 47 ms 36828 KB Output is correct
14 Correct 49 ms 37000 KB Output is correct
15 Correct 49 ms 36856 KB Output is correct
16 Correct 37 ms 35548 KB Output is correct
17 Correct 95 ms 40400 KB Output is correct
18 Correct 393 ms 63020 KB Output is correct
19 Correct 323 ms 58852 KB Output is correct
20 Correct 364 ms 62616 KB Output is correct
21 Correct 386 ms 63708 KB Output is correct
22 Correct 402 ms 64920 KB Output is correct
23 Correct 400 ms 59440 KB Output is correct
24 Correct 271 ms 59068 KB Output is correct
25 Correct 338 ms 59484 KB Output is correct
26 Correct 332 ms 58808 KB Output is correct
27 Correct 270 ms 58420 KB Output is correct
28 Correct 317 ms 59256 KB Output is correct
29 Correct 381 ms 63392 KB Output is correct
30 Correct 319 ms 58756 KB Output is correct
31 Correct 382 ms 63208 KB Output is correct
32 Incorrect 3022 ms 241900 KB Output isn't correct
33 Halted 0 ms 0 KB -