Submission #911340

# Submission time Handle Problem Language Result Execution time Memory
911340 2024-01-18T18:54:32 Z danikoynov Meetings (IOI18_meetings) C++14
19 / 100
5500 ms 52040 KB
#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;

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;*/

    for (int i = left_border[root]; i <= right_border[root]; i ++)
    {
        if (li_left_price.get_pivot(i) != left_price[i])
        {
            assert(false);
        }

                if (li_right_price.get_pivot(i) != right_price[i])
        {
            assert(false);
        }
    }
}

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);
}
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();
    build_li_chao();
    divide(root);
    vector < ll > res = get_result();
    return res;
}
/**
5 1
3 1 5 4 3
1 4

*/
# Verdict Execution time Memory Grader output
1 Correct 10 ms 43492 KB Output is correct
2 Correct 19 ms 44124 KB Output is correct
3 Correct 21 ms 44184 KB Output is correct
4 Correct 22 ms 44212 KB Output is correct
5 Correct 21 ms 44292 KB Output is correct
6 Correct 298 ms 44292 KB Output is correct
7 Correct 19 ms 44124 KB Output is correct
8 Correct 298 ms 44380 KB Output is correct
9 Correct 109 ms 44384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 10 ms 43492 KB Output is correct
2 Correct 19 ms 44124 KB Output is correct
3 Correct 21 ms 44184 KB Output is correct
4 Correct 22 ms 44212 KB Output is correct
5 Correct 21 ms 44292 KB Output is correct
6 Correct 298 ms 44292 KB Output is correct
7 Correct 19 ms 44124 KB Output is correct
8 Correct 298 ms 44380 KB Output is correct
9 Correct 109 ms 44384 KB Output is correct
10 Correct 51 ms 45024 KB Output is correct
11 Correct 95 ms 44984 KB Output is correct
12 Correct 53 ms 45008 KB Output is correct
13 Correct 102 ms 45032 KB Output is correct
14 Correct 832 ms 45264 KB Output is correct
15 Correct 48 ms 45136 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 10 ms 43356 KB Output is correct
2 Correct 2658 ms 50452 KB Output is correct
3 Execution timed out 5524 ms 52040 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 10 ms 43356 KB Output is correct
2 Correct 2658 ms 50452 KB Output is correct
3 Execution timed out 5524 ms 52040 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 10 ms 43492 KB Output is correct
2 Correct 19 ms 44124 KB Output is correct
3 Correct 21 ms 44184 KB Output is correct
4 Correct 22 ms 44212 KB Output is correct
5 Correct 21 ms 44292 KB Output is correct
6 Correct 298 ms 44292 KB Output is correct
7 Correct 19 ms 44124 KB Output is correct
8 Correct 298 ms 44380 KB Output is correct
9 Correct 109 ms 44384 KB Output is correct
10 Correct 51 ms 45024 KB Output is correct
11 Correct 95 ms 44984 KB Output is correct
12 Correct 53 ms 45008 KB Output is correct
13 Correct 102 ms 45032 KB Output is correct
14 Correct 832 ms 45264 KB Output is correct
15 Correct 48 ms 45136 KB Output is correct
16 Correct 10 ms 43356 KB Output is correct
17 Correct 2658 ms 50452 KB Output is correct
18 Execution timed out 5524 ms 52040 KB Time limit exceeded
19 Halted 0 ms 0 KB -