Submission #1064917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064917		hyakup	Meetings (IOI18_meetings)	C++17	19 / 100	5544 ms	6228 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define bug(x) cout << #x << " " << x << endl;

const ll inf = 1e9 + 10;

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
  int n = H.size(), q = L.size();
  vector<ll> resp(q);
  vector<ll> respL(n);
  for( int i = 0; i < q; i++ ){
    int l = L[i], r = R[i];
    resp[i] = inf*inf;

    stack<pair<int,ll>> pilha;
    pilha.push({ l - 1, inf });
    ll sum = 0;
    for( int j = l; j <= r; j++ ){
      while( pilha.top().second <= H[j] ){
        auto [id, v] = pilha.top(); pilha.pop();
        sum -= 1LL*v*abs(id - pilha.top().first);
      }
      sum += 1LL*H[j]*abs(j - pilha.top().first);
      pilha.push({ j, H[j] });
      respL[j] = sum;
    }

    while( !pilha.empty() ) pilha.pop();
    pilha.push({ r + 1, inf });
    sum = 0;
    for( int j = r; j >= l; j-- ){
      while( pilha.top().second <= H[j] ){
        auto [id, v] = pilha.top(); pilha.pop();
        sum -= 1LL*v*abs(id - pilha.top().first);
      }
      sum += 1LL*H[j]*abs(j - pilha.top().first);
      pilha.push({ j, H[j] });
      resp[i] = min( resp[i], sum + respL[j] - H[j] );
    }

  }
  return resp;
}

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