Submission #611606

#	Time	Username	Problem	Language	Result	Execution time	Memory
611606		cheissmart	Meetings (IOI18_meetings)	C++14	100 / 100	3480 ms	406448 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 750005;
const ll oo = 1e18;

int n, q;

bool f = false;
pi max2(pi a, pi b) {
    if(a.F != b.F) return max(a, b);
    return min(a, b);
}

pi st[N][20];
int argmax(int L, int R) { // [L, R]
    int k = __lg(R - L + 1);
    if(f)
        return max2(st[L][k], st[R - (1 << k) + 1][k]).S;
    else
        return max(st[L][k], st[R - (1 << k) + 1][k]).S;
};

ll ans[N];
vi G[N];

namespace segtree {

struct node {
    ll l_val, r_val;
    ll m, b;
    ll lz;
    int tl, tr;
    node(ll val = 0) {
        l_val = r_val = val;        
        m = b = lz = 0;
    }    
} t[N * 4];

void pull(int v) {
    t[v].l_val = t[v * 2].l_val;
    t[v].r_val = t[v * 2 + 1].r_val;
}

void apply_add(int v, ll x) {
    t[v].l_val += x, t[v].r_val += x;
    if(t[v].m) {
        t[v].b += x;
    } else {
        t[v].lz += x;
    }
}

void apply_set(int v, ll m, ll b) {
    t[v].l_val = t[v].tl * m + b;
    t[v].r_val = (t[v].tr - 1) * m + b;
    t[v].m = m, t[v].b = b;
    t[v].lz = 0;
}

void push(int v) {
    if(t[v].m) { // set
        apply_set(v * 2, t[v].m, t[v].b);
        apply_set(v * 2 + 1, t[v].m, t[v].b);
        t[v].m = t[v].b = 0;
    } else { // add
        apply_add(v * 2, t[v].lz);
        apply_add(v * 2 + 1, t[v].lz);
        t[v].lz = 0;
    }
}

void build(int v = 1, int tl = 0, int tr = n) {
    t[v] = node();
    t[v].tl = tl, t[v].tr = tr;
    if(tr - tl == 1)
        return;
    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm, tr);
}

void add(int l, int r, ll x, int v = 1, int tl = 0, int tr = n) {
    if(l <= tl && tr <= r) {
        apply_add(v, x);
        return;
    }
    push(v);
    int tm = (tl + tr) / 2;
    if(l < tm) add(l, r, x, v * 2, tl, tm);
    if(r > tm) add(l, r, x, v * 2 + 1, tm, tr);
    pull(v);
}

ll qry(int pos, int v = 1, int tl = 0, int tr = n) {
    if(tr - tl == 1)
        return t[v].l_val;
    push(v);
    int tm = (tl + tr) / 2;
    if(pos < tm) return qry(pos, v * 2, tl, tm);
    else return qry(pos, v * 2 + 1, tm, tr);
}

void cmin(int l, int r, ll m, ll b, int v = 1, int tl = 0, int tr = n) {
    if(l <= tl && tr <= r) {
        if(t[v].r_val >= m * (tr - 1) + b) {
            apply_set(v, m, b);
            return;
        }
        if(t[v].l_val <= m * tl + b)
            return;
    }
    push(v);
    int tm = (tl + tr) / 2;
    if(l < tm) cmin(l, r, m, b, v * 2, tl, tm);
    if(r > tm) cmin(l, r, m, b, v * 2 + 1, tm, tr);
    pull(v);
}

} // segtree

using namespace segtree;

int h[N], l[N], r[N];

void dfs(int L, int R) { // [L, R]
    if(L > R) return;
    int m = argmax(L, R);
    dfs(L, m - 1), dfs(m + 1, R);

    for(int i:G[m]) {
        ll cur = 1LL * (m - l[i] + 1) * h[m];
        assert(L <= l[i] && r[i] <= R);
        if(r[i] > m) cur += qry(r[i]);
        ans[i] = min(ans[i], cur);
    }
    add(m, R + 1, 1LL * (m - L + 1) * h[m]);
    if(L < m)
        cmin(m, R + 1, h[m], qry(m - 1) - 1LL * h[m] * (m - 1));
}


void solve() {
    for(int i = 0; i < n; i++)
        st[i][0] = {h[i], i};
    for(int j = 1; j < 20; j++)
        for(int i = 0; i + (1 << j) - 1 < n; i++) {
            if(f)
                st[i][j] = max2(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            else
                st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }

    for(int i = 0; i < q; i++)
        G[argmax(l[i], r[i])].PB(i);

    build();

    dfs(0, n - 1);

    for(int i = 0; i < n; i++)
        G[i].clear();
}

V<ll> minimum_costs(vi _h, vi _l, vi _r) {
    n = SZ(_h), q = SZ(_l);
    for(int i = 0; i < n; i++) h[i] = _h[i];
    for(int i = 0; i < q; i++) l[i] = _l[i], r[i] = _r[i], ans[i] = oo;

    solve();
    reverse(h, h + n);
    for(int i = 0; i < q; i++) {
        swap(l[i], r[i]);
        l[i] = n - l[i] - 1, r[i] = n - r[i] - 1;
    }
    f = true;
    solve();

    V<ll> tt;
    for(int i = 0; i < q; i++)
        tt.PB(ans[i]);
    return tt;
}

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