oj.uz

답안 #911274

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
911274 2024-01-18T17:28:49 Z danikoynov 모임들 (IOI18_meetings) C++14
19 / 100
 5500 ms 49472 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;

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.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 39260 KB Output is correct
2 Correct 11 ms 43356 KB Output is correct
3 Correct 10 ms 43356 KB Output is correct
4 Correct 10 ms 43356 KB Output is correct
5 Correct 10 ms 43352 KB Output is correct
6 Correct 12 ms 43864 KB Output is correct
7 Correct 10 ms 39516 KB Output is correct
8 Correct 11 ms 43684 KB Output is correct
9 Correct 12 ms 43612 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 39260 KB Output is correct
2 Correct 11 ms 43356 KB Output is correct
3 Correct 10 ms 43356 KB Output is correct
4 Correct 10 ms 43356 KB Output is correct
5 Correct 10 ms 43352 KB Output is correct
6 Correct 12 ms 43864 KB Output is correct
7 Correct 10 ms 39516 KB Output is correct
8 Correct 11 ms 43684 KB Output is correct
9 Correct 12 ms 43612 KB Output is correct
10 Correct 35 ms 43868 KB Output is correct
11 Correct 80 ms 43860 KB Output is correct
12 Correct 35 ms 43840 KB Output is correct
13 Correct 81 ms 44112 KB Output is correct
14 Correct 41 ms 44116 KB Output is correct
15 Correct 35 ms 43876 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 39260 KB Output is correct
2 Correct 402 ms 48992 KB Output is correct
3 Execution timed out 5504 ms 49472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 39260 KB Output is correct
2 Correct 402 ms 48992 KB Output is correct
3 Execution timed out 5504 ms 49472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 39260 KB Output is correct
2 Correct 11 ms 43356 KB Output is correct
3 Correct 10 ms 43356 KB Output is correct
4 Correct 10 ms 43356 KB Output is correct
5 Correct 10 ms 43352 KB Output is correct
6 Correct 12 ms 43864 KB Output is correct
7 Correct 10 ms 39516 KB Output is correct
8 Correct 11 ms 43684 KB Output is correct
9 Correct 12 ms 43612 KB Output is correct
10 Correct 35 ms 43868 KB Output is correct
11 Correct 80 ms 43860 KB Output is correct
12 Correct 35 ms 43840 KB Output is correct
13 Correct 81 ms 44112 KB Output is correct
14 Correct 41 ms 44116 KB Output is correct
15 Correct 35 ms 43876 KB Output is correct
16 Correct 10 ms 39260 KB Output is correct
17 Correct 402 ms 48992 KB Output is correct
18 Execution timed out 5504 ms 49472 KB Time limit exceeded
19 Halted 0 ms 0 KB -