Submission #836426

#	Time	Username	Problem	Language	Result	Execution time	Memory
836426		mousebeaver	Meetings (IOI18_meetings)	C++14	4 / 100	5592 ms	1592 KiB

meetings

#define ll long long
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

ll left(ll i)
{
    return 2*i;
}

ll right(ll i)
{
    return 2*i+1;
}

ll s[20001];

ll query(ll i, ll a, ll b, ll l, ll r)
{
    if(l <= a && b <= r)
    {
        return s[i];
    }
    if(r < a || b < l)
    {
        return 0;
    }
    ll mid = (a+b)/2;
    return max(query(left(i), a, mid, l, r), query(right(i), mid+1, b, l, r));
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) 
{
    ll n = H.size();
    ll segnodes = 1;
    while(2*n > segnodes)
    {
        segnodes *= 2;
    }
    for(ll i = 0; i <= 20000; i++)
    {
        s[i] = 0;
    }

    for(ll i = 0; i < n; i++)
    {
        s[i+segnodes/2] = H[i];
    }
    for(ll i = segnodes/2-1; i > 0; i--)
    {
        s[i] = max(s[left(i)], s[right(i)]);
    }

    vector<ll> output(0);
    for(ll i = 0; i < (ll) L.size(); i++)
    {
        ll len = R[i]+1-L[i];

        //Going from left to right:
        vector<ll> pre(len, 0);
        for(ll j = 0; j < len; j++)
        {
            if(H[L[i]+j] >= query(1, 1, segnodes/2, L[i]+1, L[i]+j+1))
            {
                //No bigger mountain before
                pre[j] = (j+1)*(ll) H[j+L[i]];
            }
            else
            {
                //Looking for last mountain bigger than this one
                ll node = segnodes/2+j+L[i];
                ll high = H[j+L[i]];
                while(high <= H[j+L[i]])
                {
                    ll par = node/2;
                    if(node == right(par))
                    {
                        high = max(high, s[left(par)]);
                    }
                    node = par;
                }
                node = left(node);
                //Go down:
                while(left(node) < segnodes)
                {
                    if(s[right(node)] > H[j+L[i]])
                    {
                        node = right(node);
                    }
                    else
                    {
                        node = left(node);
                    }
                }
                node -= segnodes/2+L[i];
                pre[j] = pre[node] + (j-node)*(ll)(H[j+L[i]]);
            }
        }

        //Going from right to left:
        vector<ll> post(len, 0);
        for(ll j = len-1; j >= 0; j--)
        {
            if(H[L[i]+j] >= query(1, 1, segnodes/2, L[i]+j+1, R[i]+1))
            {
                //No bigger mountain after that one
                post[j] = (len-j)*(ll)H[j+L[i]];
            }
            else
            {
                //Looking for first mountain bigger than this one
                ll node = segnodes/2+j+L[i];
                ll high = H[j+L[i]];
                while(high <= H[j+L[i]])
                {
                    ll par = node/2;
                    if(node == left(par))
                    {
                        high = max(high, s[right(par)]);
                    }
                    node = par;
                }
                node = right(node);
                //Go down:
                while(left(node) < segnodes)
                {
                    if(s[left(node)] > H[j+L[i]])
                    {
                        node = left(node);
                    }
                    else
                    {
                        node = right(node);
                    }
                }
                node -= segnodes/2+L[i];
                post[j] = post[node] + (node-j)*(ll)(H[j+L[i]]);
            }
        }        

        output.push_back(numeric_limits<ll>::max()/2);
        for(ll j = 0; j < len; j++)
        {
            output.back() = min(output.back(), (ll) pre[j]+post[j]-(ll)H[L[i]+j]);
        }
    }

    return output;
}

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