Submission #78675

#	Time	Username	Problem	Language	Result	Execution time	Memory
78675		imeimi2000	Meetings (IOI18_meetings)	C++17	0 / 100	175 ms	140760 KiB

meetings

#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 <= (1 << 21); ++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 <= (1 << 21); ++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;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:126:77: warning: iteration 2097152 invokes undefined behavior [-Waggressive-loop-optimizations]
     for (int i = 0; i <= (1 << 21); ++i) seg[i].l = line(0, inf), seg[i].lz = 0;
                                                                   ~~~~~~~~~~^~~
meetings.cpp:126:23: note: within this loop
     for (int i = 0; i <= (1 << 21); ++i) seg[i].l = line(0, inf), seg[i].lz = 0;
                     ~~^~~~~~~~~~~~
meetings.cpp:137:77: warning: iteration 2097152 invokes undefined behavior [-Waggressive-loop-optimizations]
     for (int i = 0; i <= (1 << 21); ++i) seg[i].l = line(0, inf), seg[i].lz = 0;
                                                                   ~~~~~~~~~~^~~
meetings.cpp:137:23: note: within this loop
     for (int i = 0; i <= (1 << 21); ++i) seg[i].l = line(0, inf), seg[i].lz = 0;
                     ~~^~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40