Submission #587465

#	Time	Username	Problem	Language	Result	Execution time	Memory
587465		definitelynotmee	Meetings (IOI18_meetings)	C++17	19 / 100	752 ms	1748 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;


std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    int Q = L.size();
    int n = H.size();
    if(ll(n)*Q <= 1e8){
        vector<ll> resp(Q);
        vector<ll> val(n);

        for(int q = 0; q < Q; q++){
            fill(val.begin()+L[q],val.begin()+R[q]+1,0);
            ll cur = 0;
            vector<pll> st;
            for(int i = L[q]; i <= R[q]; i++){
                ll ct = 1;
                while(!st.empty() && st.back().ff <= H[i]){
                    cur-=st.back().ff*st.back().ss;
                    ct+=st.back().ss;
                    st.pop_back();
                }
                cur+=ct*H[i];
                st.push_back({H[i],ct});
                val[i]+=cur;
            }

            st.clear();
            cur = 0;

            for(int i = R[q]; i >= L[q]; i--){
                val[i]+=cur;

                ll ct = 1;
                while(!st.empty() && st.back().ff <= H[i]){
                    cur-=st.back().ff*st.back().ss;
                    ct+=st.back().ss;
                    st.pop_back();
                }
                cur+=ct*H[i];
                st.push_back({H[i],ct});
            }

            resp[q] = *min_element(val.begin()+L[q],val.begin()+R[q]+1);
        }
        return resp;
    }
    return vector<ll>(1,-1);
}

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