Submission #313021

#	Time	Username	Problem	Language	Result	Execution time	Memory
313021		reymontada61	Meetings (IOI18_meetings)	C++14	17 / 100	156 ms	12208 KiB

meetings

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

int n;
const int MXN = 100005;
int arr[MXN];

int segpf[MXN * 4];
int segsf[MXN * 4];
int segans[MXN * 4];

void comb(int ind, int l, int r) {
	int m = (r + l) / 2;
	segans[ind] = max(segans[ind * 2], segans[ind * 2 + 1]);
	segsf[ind] = segsf[ind * 2 + 1];
	if (segsf[ind] == r - m) segsf[ind] += segsf[ind * 2];
	segpf[ind] = segpf[ind * 2];
	if (segpf[ind] == m - l + 1) segpf[ind] += segpf[ind * 2 + 1];
	segans[ind] = max(segans[ind], segsf[ind*2] + segpf[ind*2+1]);
}

void build(int ind, int l, int r) {
	if (l == r) {
		if (arr[l] == 1) {
			segpf[ind] = segsf[ind] = segans[ind] = 1;
		}
		return;
	}
	int m = (l + r) / 2;
	build(ind * 2, l, m);
	build(ind * 2 + 1, m+1, r);
	comb(ind, l, r);
}

int qpf[MXN * 4];
int qsf[MXN * 4];
int qns[MXN * 4];

void qcomb(int ind, int l, int r) {
	int m = (r + l) / 2;
	qns[ind] = max(qns[ind * 2], qns[ind * 2 + 1]);
	qsf[ind] = qsf[ind * 2 + 1];
	if (qsf[ind] == r - m) qsf[ind] += qsf[ind * 2];
	qpf[ind] = qpf[ind * 2];
	if (qpf[ind] == m - l + 1) qpf[ind] += qpf[ind * 2 + 1];
	qns[ind] = max(qns[ind], qsf[ind*2] + qpf[ind*2+1]);
}

void query(int ind, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) {
		qpf[ind] = segpf[ind];
		qsf[ind] = segsf[ind];
		qns[ind] = segans[ind];
		return;
	}
	if (ql > r || qr < l) {
		qpf[ind] = 0;
		qsf[ind] = 0;
		qns[ind] = 0;
		return;
	}
	int m = (l + r) / 2;
	query(ind * 2, l, m, ql, qr);
	query(ind * 2 + 1, m+1, r, ql, qr);
	qcomb(ind, l, r);
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  int Q = L.size();
  std::vector<long long> C(Q);
  
  n = H.size();
  
  for (int i=0; i<n; i++) {
	  arr[i] = H[i];
  }
  
  build(1, 0, n-1);
  
  for (int i=0; i<Q; i++) {
	  query(1, 0, n-1, L[i], R[i]);
	  C[i] = 2 * (R[i] - L[i] + 1) - qns[1];
  }
  
  return C;
  
}

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