oj.uz

Submission #221926

# Submission time Handle Problem Language Result Execution time Memory
221926 2020-04-11T13:59:09 Z IgorI Meetings (IOI18_meetings) C++17
100 / 100
 4061 ms 319944 KB 
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

const int N = 750100;

int n, q;

int H[N];
pair<int, int> sp[20][N];

pair<int, int> spmax(int l, int r, int id)
{
    int len = r - l + 1;
    int jj = H[len];
    if (id == 0)
    {
        return max(sp[jj][l], sp[jj][r - (1 << jj) + 1]);
    }
    else
    {
        if (sp[jj][l].first != sp[jj][r - (1 << jj) + 1].first)
            return max(sp[jj][l], sp[jj][r - (1 << jj) + 1]);
        else
            return min(sp[jj][l], sp[jj][r - (1 << jj) + 1]);
    }
}

bool comp1(pair<int, int> a, pair<int, int> b)
{
    if (a.first != b.first)
        return a < b;
    else
        return a > b;
}

struct Linear{
    int k;
    long long b;
};

struct Node{
    Linear line;
    int func;
    long long addition;
    long long mn;
};

Node tree[4 * N];

void Push(int V, int L, int R, int M)
{
    if (tree[V].func)
    {
        tree[2 * V + 1].func = 1;
        tree[2 * V + 1].addition = 0;
        tree[2 * V + 2].func = 1;
        tree[2 * V + 2].addition = 0;
        tree[2 * V + 1].line.b = tree[V].line.b;
        tree[2 * V + 1].line.k = tree[V].line.k;
        tree[2 * V + 2].line.b = tree[V].line.b + 1LL * (M - L) * tree[V].line.k;
        tree[2 * V + 2].line.k = tree[V].line.k;
        tree[V].func = 0;
        tree[2 * V + 1].mn = tree[2 * V + 1].line.b;
        tree[2 * V + 2].mn = tree[2 * V + 2].line.b;
    }
    else
    {
        if (tree[2 * V + 1].func)
        {
            tree[2 * V + 1].line.b += tree[V].addition;
        }
        else
        {
            tree[2 * V + 1].addition += tree[V].addition;
        }
        if (tree[2 * V + 2].func)
        {
            tree[2 * V + 2].line.b += tree[V].addition;
        }
        else
        {
            tree[2 * V + 2].addition += tree[V].addition;
        }
        tree[2 * V + 1].mn += tree[V].addition;
        tree[2 * V + 2].mn += tree[V].addition;
        tree[V].addition = 0;
    }
}

long long Get(int p, int L = 0, int R = n, int V = 0)
{
    if (p == L) return tree[V].mn;
    if (tree[V].func)
    {
        return tree[V].line.b + 1LL * (p - L) * tree[V].line.k;
    }
    if (L + 1 == R)
    {
        return tree[V].addition;
    }
    int M = (L + R) / 2;
    Push(V, L, R, M);
    if (p < M) return Get(p, L, M, 2 * V + 1);
    return Get(p, M, R, 2 * V + 2);
}

void Add(int l, int r, long long val, int L = 0, int R = n, int V = 0)
{
    if (r <= L || R <= l)
    {
        return;
    }
    if (l <= L && R <= r)
    {
        if (tree[V].func) tree[V].line.b += val;
        else tree[V].addition += val;
        tree[V].mn += val;
        return;
    }
    int M = (L + R) / 2;
    Push(V, L, R, M);
    Add(l, r, val, L, M, 2 * V + 1);
    Add(l, r, val, M, R, 2 * V + 2);
    tree[V].mn = tree[2 * V + 1].mn;
}

void Set(int l, int r, long long func_at_l, int k, int L = 0, int R = n, int V = 0)
{
    if (r <= L || R <= l)
    {
        return;
    }
    if (l <= L && R <= r)
    {
        tree[V].addition = 0;
        tree[V].func = 1;
        tree[V].line.k = k;
        tree[V].line.b = func_at_l + 1LL * (L - l) * k;
        tree[V].mn = tree[V].line.b;
        return;
    }
    int M = (L + R) / 2;
    Push(V, L, R, M);
    Set(l, r, func_at_l, k, L, M, 2 * V + 1);
    Set(l, r, func_at_l, k, M, R, 2 * V + 2);
    tree[V].mn = tree[2 * V + 1].mn;
}

int find_position(int l, int r, long long b, int k, int L = 0, int R = n, int V = 0)
{
    if (L + 1 == R) return L;
    int M = (L + R) / 2;
    Push(V, L, R, M);
    tree[V].mn = tree[2 * V + 1].mn;
    if (M <= l)
        return find_position(l, r, b, k, M, R, 2 * V + 2);
    if (r <= M)
        return find_position(l, r, b, k, L, M, 2 * V + 1);
    long long mid2_now = tree[2 * V + 2].mn;
    long long mid2_can = b + 1LL * (M - l) * k;
    if (l <= M && M < r)
    {
        if (mid2_can <= mid2_now) return find_position(l, r, b, k, M, R, 2 * V + 2);
        return find_position(l, r, b, k, L, M, 2 * V + 1);
    }
}

void Reset()
{
    for (int i = 0; i < 4 * N; i++)
    {
        tree[i].func = 0;
        tree[i].line.k = 0;
        tree[i].line.b = 0;
        tree[i].addition = 0;
        tree[i].mn = 0;
    }
}

vector<long long> solve(vector<int> h, vector<int> l, vector<int> r, int id)
{
    if (id) Reset();
    vector<int> active(n);
    vector<long long> re_ans(q);
    vector<pair<long long, int> > order;
    for (int i = 0; i < n; i++)
    {
        order.push_back({h[i], i});
    }
    if (id == 0) sort(order.begin(), order.end());
    else sort(order.begin(), order.end(), comp1);

    for (int i = 0; i < n; i++)
    {
        sp[0][i] = {h[i], i};
    }
    for (int j = 1; j < 20; j++)
    {
        for (int i = 0; i + (1 << j) - 1 < n; i++)
        {
            sp[j][i] = spmax(i, i + (1 << j) - 1, id);
        }
    }

    vector<vector<int> > queries_here(n);
    for (int j = 0; j < q; j++)
    {
        queries_here[spmax(l[j], r[j], id).second].push_back(j);
    }
    vector<int> LL(n), RR(n);

    for (auto it : order)
    {
        int L = 0, R = n - 1;
        active[it.second] = 1;
        for (int i = 0; i < queries_here[it.second].size(); i++)
        {
            int j = queries_here[it.second][i];
            re_ans[j] = Get(r[j]) + 1ll * (it.second - l[j] + 1) * it.first;
        }

        {
            int i = it.second;
            if (i > 0 && active[i - 1] == 1)
                L = LL[i - 1];
            if (i > 0 && active[i - 1] == 0)
                L = i;

            if (i + 1 < n && active[i + 1] == 1)
                R = RR[i + 1];
            if (i + 1 < n && active[i + 1] == 0)
                R = i;
        }

        RR[L] = R;
        LL[R] = L;

        long long cnt = it.second - L + 1;
        Add(it.second, R + 1, cnt * it.first);
        if (it.second > 0 && active[it.second - 1] == 1)
        {
            long long kek = Get(it.second - 1);
            int le2 = find_position(it.second, R + 1, kek + it.first, it.first);
            Set(it.second, le2 + 1, kek + it.first, it.first);
        }
    }
    return re_ans;
}

vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r)
{
    H[1] = 0, H[2] = 0, H[3] = 1;
    for (int i = 4; i < N; i++)
    {
        H[i] = H[i - 1];
        if (((i - 1) & (i - 2)) == 0)
        {
            H[i]++;
        }
    }
    n = h.size(), q = l.size();
    vector<long long> res1 = solve(h, l, r, 0);
    reverse(h.begin(), h.end());
    for (int i = 0; i < q; i++)
    {
        l[i] = n - l[i] - 1;
        r[i] = n - r[i] - 1;
        swap(l[i], r[i]);
    }
    vector<long long> res2 = solve(h, l, r, 1);
    vector<long long> ans(q);
    for (int i = 0; i < q; i++)
    {
        ans[i] = min(res1[i], res2[i]);
    }
    return ans;
}

Compilation message

meetings.cpp: In function 'std::vector<long long int> solve(std::vector<int>, std::vector<int>, std::vector<int>, int)':
meetings.cpp:221:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < queries_here[it.second].size(); i++)
                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
meetings.cpp: In function 'int find_position(int, int, long long int, int, int, int, int)':
meetings.cpp:171:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 120696 KB Output is correct
2 Correct 78 ms 121344 KB Output is correct
3 Correct 74 ms 121268 KB Output is correct
4 Correct 79 ms 121308 KB Output is correct
5 Correct 77 ms 121268 KB Output is correct
6 Correct 69 ms 121268 KB Output is correct
7 Correct 84 ms 121500 KB Output is correct
8 Correct 69 ms 121268 KB Output is correct
9 Correct 67 ms 121268 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 120696 KB Output is correct
2 Correct 78 ms 121344 KB Output is correct
3 Correct 74 ms 121268 KB Output is correct
4 Correct 79 ms 121308 KB Output is correct
5 Correct 77 ms 121268 KB Output is correct
6 Correct 69 ms 121268 KB Output is correct
7 Correct 84 ms 121500 KB Output is correct
8 Correct 69 ms 121268 KB Output is correct
9 Correct 67 ms 121268 KB Output is correct
10 Correct 77 ms 121952 KB Output is correct
11 Correct 83 ms 121956 KB Output is correct
12 Correct 84 ms 121852 KB Output is correct
13 Correct 78 ms 121836 KB Output is correct
14 Correct 85 ms 121932 KB Output is correct
15 Correct 84 ms 121936 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 120672 KB Output is correct
2 Correct 122 ms 124968 KB Output is correct
3 Correct 398 ms 145752 KB Output is correct
4 Correct 371 ms 145732 KB Output is correct
5 Correct 410 ms 147448 KB Output is correct
6 Correct 377 ms 147064 KB Output is correct
7 Correct 372 ms 146040 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 120672 KB Output is correct
2 Correct 122 ms 124968 KB Output is correct
3 Correct 398 ms 145752 KB Output is correct
4 Correct 371 ms 145732 KB Output is correct
5 Correct 410 ms 147448 KB Output is correct
6 Correct 377 ms 147064 KB Output is correct
7 Correct 372 ms 146040 KB Output is correct
8 Correct 416 ms 145552 KB Output is correct
9 Correct 358 ms 145660 KB Output is correct
10 Correct 397 ms 145796 KB Output is correct
11 Correct 401 ms 145528 KB Output is correct
12 Correct 367 ms 145632 KB Output is correct
13 Correct 394 ms 145548 KB Output is correct
14 Correct 370 ms 146040 KB Output is correct
15 Correct 337 ms 145784 KB Output is correct
16 Correct 394 ms 145656 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 120696 KB Output is correct
2 Correct 78 ms 121344 KB Output is correct
3 Correct 74 ms 121268 KB Output is correct
4 Correct 79 ms 121308 KB Output is correct
5 Correct 77 ms 121268 KB Output is correct
6 Correct 69 ms 121268 KB Output is correct
7 Correct 84 ms 121500 KB Output is correct
8 Correct 69 ms 121268 KB Output is correct
9 Correct 67 ms 121268 KB Output is correct
10 Correct 77 ms 121952 KB Output is correct
11 Correct 83 ms 121956 KB Output is correct
12 Correct 84 ms 121852 KB Output is correct
13 Correct 78 ms 121836 KB Output is correct
14 Correct 85 ms 121932 KB Output is correct
15 Correct 84 ms 121936 KB Output is correct
16 Correct 70 ms 120672 KB Output is correct
17 Correct 122 ms 124968 KB Output is correct
18 Correct 398 ms 145752 KB Output is correct
19 Correct 371 ms 145732 KB Output is correct
20 Correct 410 ms 147448 KB Output is correct
21 Correct 377 ms 147064 KB Output is correct
22 Correct 372 ms 146040 KB Output is correct
23 Correct 416 ms 145552 KB Output is correct
24 Correct 358 ms 145660 KB Output is correct
25 Correct 397 ms 145796 KB Output is correct
26 Correct 401 ms 145528 KB Output is correct
27 Correct 367 ms 145632 KB Output is correct
28 Correct 394 ms 145548 KB Output is correct
29 Correct 370 ms 146040 KB Output is correct
30 Correct 337 ms 145784 KB Output is correct
31 Correct 394 ms 145656 KB Output is correct
32 Correct 3555 ms 316940 KB Output is correct
33 Correct 3169 ms 317032 KB Output is correct
34 Correct 3664 ms 317224 KB Output is correct
35 Correct 3739 ms 317176 KB Output is correct
36 Correct 3219 ms 317140 KB Output is correct
37 Correct 3625 ms 317088 KB Output is correct
38 Correct 3615 ms 317100 KB Output is correct
39 Correct 3269 ms 317096 KB Output is correct
40 Correct 2890 ms 316964 KB Output is correct
41 Correct 3801 ms 319944 KB Output is correct
42 Correct 3951 ms 319876 KB Output is correct
43 Correct 3932 ms 319844 KB Output is correct
44 Correct 4061 ms 317092 KB Output is correct