Submission #836277

#	Time	Username	Problem	Language	Result	Execution time	Memory
836277		mousebeaver	Meetings (IOI18_meetings)	C++14	17 / 100	86 ms	13520 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;
}

struct node
{
    ll bleft;
    ll bright;
    ll bmax;
    ll len;
};

node combine(node l, node r)
{
    node output = {0, 0, 0, 0};

    if(l.bleft == l.len)
    {
        output.bleft = l.bleft + r.bleft;
    }
    else
    {
        output.bleft = l.bleft;
    }

    if(r.bright == r.len)
    {
        output.bright = r.bright+l.bright;
    }
    else
    {
        output.bright = r.bright;
    }

    output.bmax = max(max(r.bmax, l.bmax), r.bleft + l.bright);
    output.len = l.len+r.len;
    return output;
}

node query(ll i, vector<node>& s, ll a, ll b, ll l, ll r)
{
    if(l <= a && b <= r)
    {
        return s[i];
    }
    if(r < a || b < l)
    {
        return {0, 0, 0, 0};
    }

    ll mid = (a+b)/2;
    return combine(query(left(i), s, a, mid, l, r), query(right(i), s, 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;
    }
    vector<node> s(segnodes, {0, 0, 0, 1});

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

    vector<ll> output(0);
    for(ll i = 0; i < (ll) L.size(); i++)
    {
        ll mountains = R[i]+1-L[i];
        output.push_back(2*mountains - query(1, s, 1, segnodes/2, L[i]+1, R[i]+1).bmax);
    }
    return output;
}

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