Submission #292095

#	Time	Username	Problem	Language	Result	Execution time	Memory
292095		SamAnd	Meetings (IOI18_meetings)	C++17	36 / 100	1119 ms	13320 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005;

int n, qq;

vector<ll> solv2(vector<int> H, vector<int> L, vector<int> R)
{
    vector<ll> v;
    for (int ii = 0; ii < qq; ++ii)
    {
        int l = L[ii];
        int r = R[ii];

        vector<ll> ans(n);
        for (int i = l; i <= r; ++i)
            ans[i] = 0;

        stack<pair<int, int> > s;
        ll yans = 0;
        for (int i = l; i <= r; ++i)
        {
            int q = 1;
            while (!s.empty() && H[i] >= s.top().fi)
            {
                yans -= s.top().fi * 1LL * s.top().se;
                q += s.top().se;
                s.pop();
            }
            s.push(m_p(H[i], q));
            yans += s.top().fi * 1LL * s.top().se;
            ans[i] += yans;
        }

        while (!s.empty())
            s.pop();
        yans = 0;
        for (int i = r; i >= l; --i)
        {
            int q = 1;
            while (!s.empty() && H[i] >= s.top().fi)
            {
                yans -= s.top().fi * 1LL * s.top().se;
                q += s.top().se;
                s.pop();
            }
            s.push(m_p(H[i], q));
            yans += s.top().fi * 1LL * s.top().se;
            ans[i] += yans - H[i];
        }

        yans = ans[l];
        for (int i = l; i <= r; ++i)
            yans = min(yans, ans[i]);
        v.push_back(yans);
    }
    return v;
}

struct ban
{
    int l, r, ans;
    int q;
    ban()
    {
        ans = l = r = 0;
        q = 0;
    }
    ban(int x)
    {
        if (x == 1)
        {
            ans = l = r = 1;
        }
        else
        {
            ans = l = r = 0;
        }
        q = 1;
    }
};

ban t[N * 4];

ban mer(const ban& l, const ban& r)
{
    ban res;
    if (l.q == l.l)
        res.l = l.q + r.l;
    else
        res.l = l.l;
    if (r.q == r.r)
        res.r = r.q + l.r;
    else
        res.r = r.r;
    res.ans = max(l.ans, r.ans);
    res.ans = max(res.ans, l.r + r.l);
    res.q = l.q + r.q;
    return res;
}

void bil(const vector<int>& H, int tl, int tr, int pos)
{
    if (tl == tr)
    {
        t[pos] = ban(H[tl]);
        return;
    }
    int m = (tl + tr) / 2;
    bil(H, tl, m, pos * 2);
    bil(H, m + 1, tr, pos * 2 + 1);
    t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}

ban qry(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return ban();
    if (tl == l && tr == r)
        return t[pos];
    int m = (tl + tr) / 2;
    return mer(qry(tl, m, l, min(m, r), pos * 2),
               qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}

vector<ll> solv3(vector<int> H, vector<int> L, vector<int> R)
{
    bil(H, 0, n - 1, 1);
    vector<ll> v;
    for (int ii = 0; ii < qq; ++ii)
    {
        int l = L[ii];
        int r = R[ii];
        ban u = qry(0, n - 1, l, r, 1);
        v.push_back(u.ans + (r - l + 1 - u.ans) * 2);
    }
    return v;
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R)
{
    n = sz(H);
    qq = sz(L);
    if (n <= 5000 && qq <= 5000)
        return solv2(H, L, R);
    return solv3(H, L, R);
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40