Submission #139120

#	Time	Username	Problem	Language	Result	Execution time	Memory
139120		Meloric	Meetings (IOI18_meetings)	C++14	0 / 100	2 ms	256 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
#define pb push_back
#define pii pair<int, int>
#define X first
#define Y second

using namespace std;

void print(vector<int> a){
    for(auto i : a)cout << i << ' ';
    cout << '\n';
}
void pp(vector<pii> a){
    for(auto i : a)cout << i.X << ' '<< i.Y<<'|';
    cout << '\n';
}
long long comp(int l, int r, vector<int>& H){
    vector<int> ri, le;
    vector<pii> st;
    ri.assign(H.size(), 0);
    le.assign(H.size(), 0);
    int cur = 0;
    for(int i = l; i<= r; i++){
        int tmp = 1;
        while(1){
            if(st.size() == 0 || st.back().X > H[i]){
                st.pb({H[i], tmp});
                cur+= H[i]*tmp;
                le[i] = cur;
                break;
            }else{
                cur-=st.back().X * st.back().Y;
                tmp+=st.back().Y;
                st.pop_back();
            }
        }
    }
    st.clear();
    cur = 0;
    for(int i =r; i>=l; i--){
        int tmp = 1;
        while(1){
            if(st.size() == 0 || st.back().X > H[i]){
                st.pb({H[i], tmp});
                cur+= H[i]*tmp;
                ri[i] = cur;
                break;
            }else{
                cur-=st.back().X * st.back().Y;
                tmp+=st.back().Y;
                st.pop_back();
            }
        }
    }
    //print(le);
    //print(ri);
    long long ret = 1e17;
    for(int i = l; i < r; i++){
        ret = min(ret, (long long)(le[i]+ri[i+1]));
    }
    return ret;
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,
                                     vector<int> R) {
  int Q = L.size();
  vector<long long> C(Q);
  for (int j = 0; j < Q; ++j) {
    C[j] = comp(L[j], R[j], H);
  }
  return C;
}

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