제출 #911274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
911274		danikoynov	Meetings (IOI18_meetings)	C++14	19 / 100	5504 ms	49472 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];

/// Cartesian tree data
int left_child[maxn], right_child[maxn];
int left_border[maxn], right_border[maxn];
int root, depth[maxn];

void cartesian_tree()
{
    stack < int > lf;
    for (int i = 1; i <= n; i ++)
    {
        left_child[i] = -1;
        while(!lf.empty() && h[lf.top()] <= h[i])
        {
            left_child[i] = lf.top();
            lf.pop();
        }

        if (lf.empty())
            left_border[i] = 1;
        else
            left_border[i] = lf.top() + 1;

        lf.push(i);
    }

    stack < int > rf;
    for (int i = n; i >= 1; i --)
    {
        right_child[i] = -1;
        while(!rf.empty() && h[rf.top()] < h[i])
        {
            right_child[i] = rf.top();
            rf.pop();
        }

        if (rf.empty())
            right_border[i] = n;
        else
            right_border[i] = rf.top() - 1;

        rf.push(i);
    }

    for (int i = 1; i <= n; i ++)
    {
        if (left_border[i] == 1 && right_border[i] == n)
        {
            root = i;
            break;
        }
    }
}

void calc_depth(int ver)
{
    //cout << "vertex " << ver << endl;
    //cout << "left border " << left_border[ver] << " right border " << right_border[ver] << endl;
    if (left_child[ver] != -1)
    {
        depth[left_child[ver]] = depth[ver] + 1;
        calc_depth(left_child[ver]);
    }
    if (right_child[ver] != -1)
    {
        depth[right_child[ver]] = depth[ver] + 1;
        calc_depth(right_child[ver]);
    }
}


struct query
{
    int l, r, idx;

    query(int _l = 0, int _r = 0, int _idx = 0)
    {
        l = _l;
        r = _r;
        idx = _idx;
    }
};

query task[maxn];
vector < query > spot[maxn];

struct line
{
    ll k, m;

    line (ll _k = 0, ll _m = 0)
    {
        k = _k;
        m = _m;
    }

    ll get(ll x)
    {
        return k * x + m;
    }
};


void assign_queries()
{
    for (int i = 1; i <= q; i ++)
    {
        int mx = -1;
        for (int j = task[i].l; j <= task[i].r; j ++)
        {
            if (mx == -1 || depth[j] < depth[mx])
                mx = j;
        }
        spot[mx].push_back(task[i]);
    }
}

const ll inf = 1e18;

ll left_price[maxn], right_price[maxn];
ll answer[maxn];

void chmin(ll &var, ll val)
{
    var = min(var, val);
}


void conquer(int root)
{
line left_line(h[root], - (root - 1) * h[root]), right_line(- h[root], + (root + 1) * h[root]);
    if (root != left_border[root])
        left_line.m += left_price[root - 1];
    if (root != right_border[root])
        right_line.m += right_price[root + 1];


    if (root == left_border[root])
        left_price[root] = h[root];
    else
        left_price[root] = left_price[root - 1] + h[root];



    for (int pivot = root + 1; pivot <= right_border[root]; pivot ++)
    {
        left_price[pivot] += (root - left_border[root] + 1) * h[root];
        chmin(left_price[pivot], left_line.get(pivot));
    }

    if (root == right_border[root])
        right_price[root] = h[root];
    else
        right_price[root] = right_price[root + 1] + h[root];

    for (int pivot = root - 1; pivot >= left_border[root]; pivot --)
    {
        right_price[pivot] += (right_border[root] - root + 1) * h[root];
        chmin(right_price[pivot], right_line.get(pivot));
    }
}
void divide(int root)
{
    if (left_child[root] != -1)
        divide(left_child[root]);
    if (right_child[root] != -1)
        divide(right_child[root]);

    for (query cur : spot[root])
    {
        ///cout << "answer " << left_border[root] << " " << right_border[root] << " " << cur.idx << endl;
        ll left_opt = right_price[cur.l] + (ll)(cur.r - root + 1) * h[root];
        ll right_opt = (ll)(root - cur.l + 1) * h[root] + left_price[cur.r];
         chmin(answer[cur.idx], min(left_opt, right_opt));
    }

    conquer(root);

    /**cout << "range " << left_border[root] << " " << right_border[root] << endl;
    for (int i = left_border[root]; i <= right_border[root]; i ++ )
        cout << left_price[i] << " ";
    cout << endl;
    for (int i = left_border[root]; i <= right_border[root]; i ++ )
                cout << right_price[i] << " ";
    cout << endl;*/
}

vector < ll > get_result()
{
    vector < ll > res;
    for (int i = 1; i <= q; i ++)
        res.push_back(answer[i]);
    return res;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,
                                vector<int> R)
{
    n = H.size();
    q = L.size();
    for (int i = 1; i <= n; i ++)
    {
        h[i] = H[i - 1];
    }

    for (int i = 1; i <= q; i ++)
    {
        task[i] = query(L[i - 1] + 1, R[i - 1] + 1, i);
        answer[i] = inf;
    }

    cartesian_tree();
    calc_depth(root);
    assign_queries();
    divide(root);
    vector < ll > res = get_result();
    return res;
}

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