Submission #1064929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064929		hyakup	Meetings (IOI18_meetings)	C++17	0 / 100	25 ms	3288 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);
  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: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40