Submission #1123725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123725		Pacybwoah	Meetings (IOI18_meetings)	C++20	19 / 100	5592 ms	7700 KiB

meetings

#include "meetings.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;
typedef long long ll;
namespace{
    int n, q;
    vector<ll> vec;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
    n = H.size();
    q = L.size();
    vec.resize(n + 1);
    for(int i = 1; i <= n; i++) vec[i] = H[i - 1];
    vector<ll> fans(q, 1e18);
    for(int hey = 0; hey < q; hey++){
        int l = L[hey] + 1, r = R[hey] + 1;
        vector<ll> ans(n + 1), anss(n + 1);
        vector<pair<pair<int, int>, ll>> st;
        for(int i = l; i <= r; i++){
            ans[i] = ans[i - 1] + vec[i];
            int nowl = i;
            while(!st.empty() && st.back().second < vec[i]){
                ans[i] -= st.back().second * (st.back().first.second - st.back().first.first + 1);
                ans[i] += vec[i] * (st.back().first.second - st.back().first.first + 1);
                nowl = st.back().first.first;
                st.pop_back();
            }
            st.push_back(make_pair(make_pair(nowl, i), vec[i]));
        }
        vector<pair<pair<int, int>, ll>>().swap(st);
        for(int i = r; i >= l; i--){
            if(i < r) anss[i] = anss[i + 1] + vec[i];
            else anss[i] = vec[i];
            int nowl = i;
            while(!st.empty() && st.back().second < vec[i]){
                anss[i] -= st.back().second * (st.back().first.second - st.back().first.first + 1);
                anss[i] += vec[i] * (st.back().first.second - st.back().first.first + 1);
                nowl = st.back().first.second;
                st.pop_back();
            }
            st.push_back(make_pair(make_pair(i, nowl), vec[i]));
        }
        for(int i = l; i <= r; i++){
            fans[hey] = min(fans[hey], ans[i] + anss[i] - vec[i]);
            //cout << hey << " " << i << " " << ans[i] << ' ' << anss[i] << " " << vec[i] << "\n";
        }
    }
    return fans;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run grader.cpp meetings.cpp

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