Submission #1209409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209409		Aviansh	Meetings (IOI18_meetings)	C++20	19 / 100	5594 ms	1604 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

vector<long long> minimum_costs(vector<int> h, vector<int> L, vector<int> R) {
    int q = L.size();
    int n = h.size();
    vector<long long>ansr(q);
    for(int i = 0;i<q;i++){
        long long ans[n];
        fill(ans,ans+n,0);
        set<array<int,2>>s;
        for(int j = L[i];j<=R[i];j++){
            auto it = s.lower_bound({h[j],-1});
            if(s.size()&&it!=s.end()){
                array<int,2>a = *it;
                ans[j]+=ans[a[1]]+1LL*h[j]*(j-a[1]);
            }
            else{
                ans[j]+=1LL*h[j]*(j+1-L[i]);
            }
            while(s.size()&&(*s.begin())[0]<=h[j]){
                s.erase(s.begin());
            }
            s.insert({h[j],j});
        }
        s.clear();
        long long cans[n];
        fill(cans,cans+n,0);
        for(int j = R[i];j>=L[i];j--){
            auto it = s.lower_bound({h[j],-1});
            if(s.size()&&it!=s.end()){
                array<int,2>a = *it;
                ans[j]+=cans[a[1]]+1LL*h[j]*(a[1]-j-1);
                cans[j]=cans[a[1]]+1LL*h[j]*(a[1]-j);
            }
            else{
                ans[j]+=1LL*h[j]*(R[i]-j);
                cans[j]=1LL*h[j]*(R[i]-j+1);
            }
            while(s.size()&&(*s.begin())[0]<=h[j]){
                s.erase(s.begin());
            }
            s.insert({h[j],j});
        }
        ansr[i]=2e18;
        for(int j = L[i];j<=R[i];j++){
            ansr[i]=min(ansr[i],ans[j]);
        }
    }
    return ansr;
}

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