Submission #1031728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031728		HappyCapybara	Meetings (IOI18_meetings)	C++17	0 / 100	4305 ms	2524 KiB

meetings

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

#define ll long long

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
  int Q = L.size();
  int N = H.size();
  vector<ll> C(Q, pow(10, 18));
  for (int i=0; i<Q; i++){
    if (L[i] == R[i]){
      C[i] = H[i];
      continue;
    }
    stack<pair<ll,int>> s;
    vector<ll> lv(N, 0), rv(N, 0);
    for (int j=L[i]; j<=R[i]; j++){
      if (s.empty()){
        s.push({H[j], j});
        lv[j] += H[j];
        continue;
      }
      lv[j] = lv[j-1];
      while (!s.empty() && H[j] > s.top().first){
        int x = s.top().first, y = s.top().second;
        s.pop();
        if (s.empty()) lv[j] -= x*(ll) (y-L[i]+1);
        else lv[j] -= x*(ll) (y-s.top().second);
      }
      if (s.empty()) lv[j] += H[j]*(ll) (j-L[i]+1);
      else lv[j] += H[j]*(ll) (j-s.top().second);
      s.push({H[j], j});
      //cout << j << " " << lv[j] << "\n";
    }

    while (!s.empty()) s.pop();
    for (int j=R[i]; j>=L[i]; j--){
      if (s.empty()){
        s.push({H[j], j});
        rv[j] += H[j];
        continue;
      }
      rv[j] = rv[j+1];
      while (!s.empty() && H[j] > s.top().first){
        int x = s.top().first, y = s.top().second;
        s.pop();
        if (s.empty()) rv[j] -= x*(ll) (R[i]-y+1);
        else rv[j] -= x*(ll) (s.top().second-y);
      }
      if (s.empty()) rv[j] += H[j]*(ll) (R[i]-j+1);
      else rv[j] += H[j]*(ll) (s.top().second-j);
      s.push({H[j], j});
      //cout << j << " " << rv[j] << "\n";
    }
    for (int j=L[i]; j<=R[i]; j++) C[i] = min(C[i], lv[j]-H[j]+rv[j]);
  }
  return C;
}

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