Submission #1064931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064931		hyakup	Meetings (IOI18_meetings)	C++17	19 / 100	3449 ms	7760 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;

const int maxn = 1e5 + 10;

vector<int> seg( 4*maxn );
void build( int pos, int ini, int fim, vector<int>& idL, vector<int>& idR ){
  if( ini == fim ){ seg[pos] = idR[ini] - idL[ini] - 1; return; }
  int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
  build( l, ini, mid, idL, idR );
  build( r, mid + 1, fim, idL, idR );
  seg[pos] = max( seg[l], seg[r] );
}

int query( int pos, int ini, int fim, int ki, int kf ){
  if( ki > fim || ini > kf ) return 0;
  if( ki <= ini && fim <= kf ) return seg[pos];
  int mid = ( ini + fim )/2;
  return max( query( 2*pos, ini, mid, ki, kf ), query( 2*pos + 1, mid + 1, fim, ki, kf ) );
}

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);
  if( q <= 50000 ){

    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; 
  }
  vector<int> idL(n), idR(n);
  idL[0] = (( H[0] == 2 ) ? 0 : -1 );
  for( int i = 1; i < n; i++ ) idL[i] = (( H[i] == 2 ) ? i : idL[i - 1] );
  idR[n - 1] = (( H[n - 1] == 2 ) ? n - 1 : n );
  for( int i = n - 2; i >= 0; i-- ) idR[i] = (( H[i] == 2 ) ? i : idR[i + 1] );


  build( 1, 0, n - 1, idL, idR );

  for( int i = 0; i < q; i++ ){
    int l = L[i], r = R[i];
    resp[i] = 2*(r - l + 1) - max({ idR[l] - l, r - idL[r], query( 1, 0, n - 1, idR[l], idL[r] ) });
  }
  return resp;
}

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