제출 #740422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
740422		danikoynov	Meetings (IOI18_meetings)	C++14	36 / 100	661 ms	53196 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 7.5e5 + 10;
int n, q;
ll h[maxn];

ll calc(int pivot, int left, int right)
{
    ll mx = 0, ans = 0;
    for (int i = pivot; i >= left; i --)
    {
        mx = max(mx, h[i]);
        ans += mx;
    }

    mx = h[pivot];
    for (int i = pivot + 1; i <= right; i ++)
    {
        mx = max(mx, h[i]);
        ans += mx;
    }

    return ans;
}


ll pref[maxn], suff[maxn];
ll query(int left, int right)
{
    ll ans = 1e18;

    /**for (int pivot = left; pivot <= right; pivot ++)
    {
        ll cur = calc(pivot, left, right);
        cout << cur << " ";
        ans = min(ans, calc(pivot, left, right));
    }
    cout << endl;*/

    stack < int > st;
    ll sum = 0;
    for (int i = left; i <= right; i ++)
    {
        while(!st.empty() && h[st.top()] < h[i])
        {
            int val = st.top();
            st.pop();
            int bef = left - 1;
            if (!st.empty())
                bef = st.top();
            sum = sum - (ll)(val - bef) * h[val];
        }

        int bef = left - 1;
        if (!st.empty())
        {
            bef = st.top();
        }
        sum = sum + (ll)(i - bef) * h[i];

        st.push(i);

        pref[i] = sum;
        ///cout << pref[i] << " ";
    }
    ///cout << endl;

    while(!st.empty())
        st.pop();
    sum = 0;
    for (int i = right; i >= left; i --)
    {
        while(!st.empty() && h[st.top()] < h[i])
        {
            int val = st.top();
            st.pop();
            int aft = right + 1;
            if (!st.empty())
                aft = st.top();
            sum = sum - (ll)(aft - val) * h[val];
        }

        int aft = right + 1;
        if (!st.empty())
        {
            aft = st.top();
        }
        sum = sum + (ll)(aft - i) * h[i];

        st.push(i);
        suff[i] = sum;
    }

    for (int i = left; i <= right; i ++)
    {
        ans = min(ans, pref[i] + suff[i] - h[i]);
    }

    return ans;
}

struct node
{
    int lf, rf, sz, mx;

    node(int _lf = 0, int _rf = 0, int _sz = 0, int _mx = 0)
    {
        lf = _lf;
        rf = _rf;
        sz = _sz;
        mx = _mx;
    }
};

node merge_node(node l, node r)
{
    node m;
    m.mx = max(max(l.mx, r.mx), l.rf + r.lf);
    m.lf = l.lf;
    if (l.lf == l.sz)
        m.lf = l.lf + r.lf;
    m.rf = r.rf;
    if (r.rf == r.sz)
        m.rf = r.rf + l.rf;
    m.sz = l.sz + r.sz;
    return m;
}

node tree[4 * maxn];
void build(int root, int left, int right)
{
    if (left == right)
    {
        if (h[left] == 1)
        {
            tree[root] = node(1, 1, 1, 1);
        }
        else
        {
            tree[root] = node(0, 0, 1, 0);
        }
        return;
    }

    int mid = (left + right) / 2;
    build(root * 2, left, mid);
    build(root * 2 + 1, mid + 1, right);
    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

node query_range(int root, int left, int right, int qleft, int qright)
{
    if (left > qright || right < qleft)
        return node();

    if (left >= qleft && right <= qright)
        return tree[root];

    int mid = (left + right) / 2;
    return merge_node(query_range(root * 2, left, mid, qleft, qright),
                      query_range(root * 2 + 1, mid + 1, right, qleft, qright));
}

vector<long long> minimum_costs(vector<int> H, vector<int> L,
                                vector<int> R)
{
    n = H.size();
    q = L.size();
    for (int i = 0; i < n; i ++)
    {
        h[i] = H[i];
    }

    vector < ll > res(q);
    build(1, 0, n - 1);
    for (int i = 0; i < q; i ++)
    {
        if (n <= 5000 && q <= 5000)
            res[i] = query(L[i], R[i]);
        else
        {
            node cur = query_range(1, 0, n - 1, L[i], R[i]);
            ll ans = (R[i] - L[i] + 1) * 2 - cur.mx;
            res[i] = ans;
        }
    }
    return res;
}

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