Submission #911331

# Submission time Handle Problem Language Result Execution time Memory
911331 2024-01-18T18:49:11 Z danikoynov Meetings (IOI18_meetings) C++14
19 / 100
5500 ms 51548 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 = li_right_price.get_pivot(cur.l) + (ll)(cur.r - root + 1) * h[root];
        ll left_opt = right_price[cur.l] + (ll)(cur.r - root + 1) * h[root];
        //ll right_opt = (ll)(root - cur.l + 1) * h[root] + 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 9 ms 41304 KB Output is correct
2 Correct 19 ms 44308 KB Output is correct
3 Correct 18 ms 44568 KB Output is correct
4 Correct 20 ms 44124 KB Output is correct
5 Correct 20 ms 44120 KB Output is correct
6 Correct 284 ms 44408 KB Output is correct
7 Correct 18 ms 42080 KB Output is correct
8 Correct 294 ms 44380 KB Output is correct
9 Correct 119 ms 44124 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 9 ms 41304 KB Output is correct
2 Correct 19 ms 44308 KB Output is correct
3 Correct 18 ms 44568 KB Output is correct
4 Correct 20 ms 44124 KB Output is correct
5 Correct 20 ms 44120 KB Output is correct
6 Correct 284 ms 44408 KB Output is correct
7 Correct 18 ms 42080 KB Output is correct
8 Correct 294 ms 44380 KB Output is correct
9 Correct 119 ms 44124 KB Output is correct
10 Correct 50 ms 45024 KB Output is correct
11 Correct 95 ms 44976 KB Output is correct
12 Correct 55 ms 45160 KB Output is correct
13 Correct 101 ms 45136 KB Output is correct
14 Correct 842 ms 45324 KB Output is correct
15 Correct 47 ms 45136 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 10 ms 41308 KB Output is correct
2 Correct 2667 ms 50400 KB Output is correct
3 Execution timed out 5548 ms 51548 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 10 ms 41308 KB Output is correct
2 Correct 2667 ms 50400 KB Output is correct
3 Execution timed out 5548 ms 51548 KB Time limit exceeded
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 9 ms 41304 KB Output is correct
2 Correct 19 ms 44308 KB Output is correct
3 Correct 18 ms 44568 KB Output is correct
4 Correct 20 ms 44124 KB Output is correct
5 Correct 20 ms 44120 KB Output is correct
6 Correct 284 ms 44408 KB Output is correct
7 Correct 18 ms 42080 KB Output is correct
8 Correct 294 ms 44380 KB Output is correct
9 Correct 119 ms 44124 KB Output is correct
10 Correct 50 ms 45024 KB Output is correct
11 Correct 95 ms 44976 KB Output is correct
12 Correct 55 ms 45160 KB Output is correct
13 Correct 101 ms 45136 KB Output is correct
14 Correct 842 ms 45324 KB Output is correct
15 Correct 47 ms 45136 KB Output is correct
16 Correct 10 ms 41308 KB Output is correct
17 Correct 2667 ms 50400 KB Output is correct
18 Execution timed out 5548 ms 51548 KB Time limit exceeded
19 Halted 0 ms 0 KB -