Submission #1016152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016152		Unforgettablepl	Meetings (IOI18_meetings)	C++17	19 / 100	5581 ms	3140 KiB

meetings

#include <bits/stdc++.h>
using namespace std;
#include "meetings.h"

const int SQRT = 140;

struct Query{
    int L,R,idx;
    Query(int L,int R,int idx):L(L),R(R),idx(idx){}
    bool operator<(const Query& other)const{
        return L/SQRT == other.L/SQRT ? R<other.R : L<other.L;
    }
};

std::vector<long long> minimum_costs(vector<int> H, vector<int> L,
                                     vector<int> R) {
    int n = H.size();
    int q = L.size();
    vector<long long> cost(n);
    auto add = [&](int x,int offset){
        int maxi = H[x];
        for(int i=x;i>=0;i--){
            maxi = max(maxi,H[i]);
            cost[i]+=offset*maxi;
        }
        maxi = H[x];
        for(int i=x+1;i<n;i++){
            maxi = max(maxi,H[i]);
            cost[i]+=offset*maxi;
        }
    };
    int l = 0;
    int r = -1;
    vector<long long> ans(q);
    vector<Query> queries;
    for(int i=0;i<q;i++)queries.emplace_back(L[i],R[i],i);
    sort(queries.begin(),queries.end());
    for(auto[tarL,tarR,idx]:queries){
        while(l<tarL)add(l++,-1);
        while(tarL<l)add(--l,1);
        while(r<tarR)add(++r,1);
        while(tarR<r)add(r--,-1);
        ans[idx] = INT64_MAX;
        for(int i=tarL;i<=tarR;i++)ans[idx]=min(ans[idx],cost[i]);
    }
    return ans;
}

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