Submission #221926

#	Time	Username	Problem	Language	Result	Execution time	Memory
221926		IgorI	Meetings (IOI18_meetings)	C++17	100 / 100	4061 ms	319944 KiB

meetings

#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 (stderr)

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 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 40 / 40