Submission #1182451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182451		HappyCapybara	Meetings (IOI18_meetings)	C++17	17 / 100	254 ms	31736 KiB

meetings

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

#define ll long long

int N;
vector<vector<ll>> st;

vector<ll> merge(vector<ll> l, vector<ll> r){
  vector<ll> res(4, 0);
  res[3] = l[3]+r[3];
  res[0] = max(max(l[0], r[0]), l[2]+r[1]);
  if (l[1] == l[3]) res[1] = l[1]+r[1];
  else res[1] = l[1];
  if (r[2] == r[3]) res[2] = l[2]+r[2];
  else res[2] = r[2];
  return res;
}

void update(int pos, int val, int node=1, int tl=0, int tr=N-1){
  if (tl == tr){
    st[node] = {val, val, val, 1};
    return;
  }
  int tm = (tl+tr)/2;
  if (pos <= tm) update(pos, val, node*2, tl, tm);
  else update(pos, val, node*2+1, tm+1, tr);
  st[node] = merge(st[node*2], st[node*2+1]);
}

vector<ll> query(int l, int r, int node=1, int tl=0, int tr=N-1){
  if (tr < l || r < tl) return {0, 0, 0, 0};
  if (l <= tl && tr <= r) return st[node];
  int tm = (tl+tr)/2;
  return merge(query(l, r, node*2, tl, tm), query(l, r, node*2+1, tm+1, tr));
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
  N = H.size();
  int Q = L.size();
  st.resize(4*N, vector<ll>(4, 0));
  for (int i=0; i<N; i++){
    if (H[i] == 1) update(i, 1);
    else update(i, 0);
  }
  vector<ll> C(Q);
  for (int i=0; i<Q; i++) C[i] = 2*(R[i]-L[i]+1)-query(L[i], R[i])[0];
  return C;
}

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