Submission #911345

#	Time	Username	Problem	Language	Result	Execution time	Memory
911345		danikoynov	Meetings (IOI18_meetings)	C++14	100 / 100	3182 ms	396404 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;
    }
};




const ll inf = 1e18;

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


struct li_chao_tree
{
    struct node
    {
        line cur;
        ll lazy;
        bool act;
        node *lc, *rc;

        node()
        {
            cur = line();
            act = false;
            lc = NULL;
            rc = NULL;
            lazy = 0;
        }
    };


    node *root = NULL;

    li_chao_tree()
    {
        root = new node();
    }
    void push_lazy(node *ver)
    {
        if (ver -> act)
            ver -> cur.m += ver -> lazy;

        if (ver -> lc != NULL)
            ver -> lc -> lazy += ver -> lazy;
        if (ver -> rc != NULL)
            ver -> rc -> lazy += ver -> lazy;

        ver -> lazy = 0;
    }

    void add_line_conscious(node *ver, ll left, ll right, line target)
    {
        push_lazy(ver);

        if (ver -> act == false)
        {
            ver -> act = true;
            ver -> cur = target;
            return;
        }

        ll mid = (left + right) / 2;
        if (ver -> cur.get(mid) > target.get(mid))
            swap(ver -> cur, target);

        if (left == right)
            return;

        if (ver -> cur.get(left) > target.get(left))
            add_line_conscious(ver -> lc, left, mid, target);
        if (ver -> cur.get(right) > target.get(right))
            add_line_conscious(ver -> rc, mid + 1, right, target);
    }

    void add_line(node *ver, ll left, ll right, ll qleft, ll qright, line target)
    {
        push_lazy(ver);

        if (left > qright || right < qleft || qright < qleft)
            return;

        if (left >= qleft && right <= qright)
        {
            add_line_conscious(ver, left, right, target);
            return;
        }

        ll mid = (left + right) / 2;
        add_line(ver -> lc, left, mid, qleft, qright, target);
        add_line(ver -> rc, mid + 1, right, qleft, qright, target);
    }

    void range_update(node *ver, ll left, ll right, ll qleft, ll qright, ll val)
    {

        push_lazy(ver);
        if (left > qright || right < qleft || qright < qleft)
            return;

        if (left >= qleft && right <= qright)
        {
            ver -> lazy += val;
            push_lazy(ver);
            return;
        }

        ll mid = (left + right) / 2;
        if (left != right && ver -> act)
        {
            ///cout << "add conscious " << " " << left << " " << mid << " " <<
            add_line_conscious(ver -> lc, left, mid, ver -> cur);
            add_line_conscious(ver -> rc, mid + 1, right, ver -> cur);
            ver -> act = false;
        }
        range_update(ver -> lc, left, mid, qleft, qright, val);
        range_update(ver -> rc, mid + 1, right, qleft, qright, val);
        ///cout << "range update " << left << " " << right << " " << qleft << " " << qright << " " << ver -> act << endl;
    }

    ll query_pivot(node *ver, ll left, ll right, ll pivot)
    {
        push_lazy(ver);
        ll mx = inf;
        if (ver -> act)
            chmin(mx, ver -> cur.get(pivot));
        if (left == right)
            return mx;

        ll mid = (left + right) / 2;
        if (pivot <= mid)
            chmin(mx, query_pivot(ver -> lc, left, mid, pivot));
        else
            chmin(mx, query_pivot(ver -> rc, mid + 1, right, pivot));

        return mx;

    }

    void build(node *ver, ll left, ll right)
    {
        if (left == right)
            return;

        ver -> lc = new node();
        ver -> rc = new node();

        ll mid = (left + right) / 2;
        build(ver -> lc, left, mid);
        build(ver -> rc, mid + 1, right);
    }

    ll get_pivot(ll pivot)
    {
        return query_pivot(root, 1, n, pivot);
    }

    void insert_line(int left, int right, line cur)
    {
        add_line(root, 1, n, left, right, cur);
    }

    void add_to_range(int left, int right, ll val)
    {
        range_update(root, 1, n, left, right, val);
    }
};
ll left_price[maxn], right_price[maxn];
li_chao_tree li_left_price, li_right_price;

ll answer[maxn];



void conquer(ll 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];
        left_line.m += li_left_price.get_pivot(root - 1);
    }
    if (root != right_border[root])
    {
        ///right_line.m += right_price[root + 1];
        right_line.m += li_right_price.get_pivot(root + 1);
    }


    if (root == left_border[root])
    {
        ///cout << "conquer " << h[root] << endl;
        li_left_price.insert_line(root, root, line(0, h[root]));
        ///left_price[root] = h[root];
    }
    else
    {
        li_left_price.insert_line(root, root, line(0, li_left_price.get_pivot(root - 1) + h[root]));
        ///left_price[root] = left_price[root - 1] + h[root];
    }


        //if (root == 1)
        //cout << "first " << li_left_price.get_pivot(2) << endl;

    li_left_price.add_to_range(root + 1, right_border[root], (root - left_border[root] + 1) * h[root]);
    li_left_price.insert_line(root + 1, right_border[root], left_line);

    /**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])
    {
        li_right_price.insert_line(root, root, line(0, h[root]));
        ///right_price[root] = h[root];
    }
    else
    {
        li_right_price.insert_line(root, root, line(0, li_right_price.get_pivot(root + 1) + h[root]));
        ///right_price[root] = right_price[root + 1] + h[root];
    }


    li_right_price.add_to_range(left_border[root], root - 1, (right_border[root] - root + 1) * h[root]);
    li_right_price.insert_line(left_border[root], root - 1, right_line);
    /**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 = (ll)(cur.r - root + 1) * h[root];
        if (root != cur.l)
            left_opt += li_right_price.get_pivot(cur.l);

        //ll left_opt = right_price[cur.l] + (ll)(cur.r - root + 1) * h[root];
        ll right_opt = (ll)(root - cur.l + 1) * h[root];
        if (root != cur.r)
            right_opt += + li_left_price.get_pivot(cur.r);;
        ///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 << li_left_price.get_pivot(i) << " ";
    cout << endl;
    for (int i = left_border[root]; i <= right_border[root]; i ++ )
        cout << li_right_price.get_pivot(i) << " ";
    cout << endl;
    cout << "-------------" << 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;
}

void build_li_chao()
{
    li_left_price.build(li_left_price.root, 1, n);
    li_right_price.build(li_right_price.root, 1, n);
}

int tree[4 * maxn];

void build_tree(int root, int left, int right)
{
    if (left == right)
    {
        tree[root] = left;
        return;
    }

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);

    tree[root] = tree[root * 2];
    if (depth[tree[root * 2 + 1]] < depth[tree[root]])
        tree[root] = tree[root * 2 + 1];
}

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

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

    int mid = (left + right) / 2;
    int lf = query_depth(root * 2, left, mid, qleft, qright);
    int rf = query_depth(root * 2 + 1, mid + 1, right, qleft, qright);

    if (depth[lf] < depth[rf])
        return lf;
    return rf;
}


void assign_queries()
{
    for (int i = 1; i <= q; i ++)
    {
        int mx = query_depth(1, 1, n, task[i].l, task[i].r);
        /**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]);
    }
}
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);
    depth[0] = 1e6 + 10;
    build_tree(1, 1, n);
    assign_queries();
    build_li_chao();
    divide(root);
    vector < ll > res = get_result();
    return res;
}
/**
5 1
3 1 5 4 3
1 4

*/

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