Submission #759757

#	Time	Username	Problem	Language	Result	Execution time	Memory
759757		alexander707070	Meetings (IOI18_meetings)	C++14	19 / 100	5578 ms	5884 KiB

meetings

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

const int inf=1e9+7;

int n,h[MAXN],q,l,r,mins;
long long res[MAXN],curr;
vector< pair<int,int> > st;
vector<long long> ans;


vector<long long> minimum_costs(vector<int> H,vector<int> L,vector<int> R){
    n=int(H.size()); q=int(L.size());

    for(int i=1;i<=n;i++){
        h[i]=H[i-1];
    }

    for(int i=0;i<q;i++){
        l=L[i]+1; r=R[i]+1;

        st.clear(); curr=0;
        st.push_back({inf,l-1});

        for(int f=l;f<=r;f++){
            while(h[f]>=st.back().first){
                curr-=(long long) st.back().first*(st.back().second-st[st.size()-2].second);
                st.pop_back();
            }
            curr+=(long long) h[f]*(f-st.back().second);
            res[f]=curr;

            st.push_back({h[f],f});
        }

        st.clear(); curr=0;
        st.push_back({inf,r+1});

        for(int f=r;f>=l;f--){
            while(h[f]>=st.back().first){
                curr-=(long long) st.back().first*(-st.back().second+st[st.size()-2].second);
                st.pop_back();
            }
            curr+=(long long) h[f]*(st.back().second-f);
            res[f]+=curr-h[f];
            
            st.push_back({h[f],f});
        }

        mins=l;
        for(int f=l+1;f<=r;f++){
            if(res[f]<res[mins])mins=f;
        }

        ans.push_back(res[mins]);
    }

    return ans;
}

/*
int main(){
     minimum_costs({2, 4, 3, 5}, {0, 1}, {2, 3});

     for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
     }
}
*/

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