Submission #836448

#	Time	Username	Problem	Language	Result	Execution time	Memory
836448		mousebeaver	Meetings (IOI18_meetings)	C++14	4 / 100	5579 ms	1464 KiB

meetings

    #pragma GCC optimize("-O3")
    #define ll long long
    #include "meetings.h"
    #include <bits/stdc++.h>
    using namespace std;
     
    int left(int i)
    {
        return 2*i;
    }
     
    int right(int i)
    {
        return 2*i+1;
    }
     
    int s[20001];
     
    int 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:
            ll pre[len];
            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];
                    int 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:
            ll post[len];
            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];
                    int 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