제출 #1135588

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1135588		alterio	모임들 (IOI18_meetings)	C++20	17 / 100	94 ms	16456 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int mxn = 1e5 + 100;

struct Node {
	ll prf = 0, suf = 0, sum = 0, mx = 0;

	bool operator == (Node a) {
		return (a.prf == prf && a.suf == suf && a.sum == sum && a.mx == mx);
	}

} null;

Node operator + (Node a, Node b) {
	if (a == null) return b;
	if (b == null) return a;
	ll prf = a.prf;
	if (a.mx == 1) prf += b.prf;
	ll suf = b.suf;
	if (b.mx == 1) suf += a.suf;
	return {prf, suf, max({a.sum, b.sum, a.suf + b.prf}), max(a.mx, b.mx)};
}

vector<int> a;

struct SGT {

	vector<Node> sgt;

	SGT(int sz) {
		sgt.resize(4 * sz);
	}

	void build(int k, int l, int r) {
		if (l == r) {
			sgt[k] = {a[l] == 1, a[l] == 1, a[l] == 1, a[l]};
			return;
		}
		int mid = (l + r) / 2;
		build(k * 2, l, mid);
		build(k * 2 + 1, mid + 1, r);
		sgt[k] = sgt[k * 2] + sgt[k * 2 + 1];
	}
	
	Node get(int k, int l, int r, int i, int j) {
		if (l > j || r < i) return null;
		if (i <= l && r <= j) return sgt[k];
		int mid = (l + r) / 2;
		return get(k * 2, l, mid, i, j) + get(k * 2 + 1, mid + 1, r, i, j);
	}
} sgt(mxn);

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    int N = H.size(), Q = L.size();
	a = H;
    vector<ll> C(Q);
	sgt.build(1, 0, N - 1);
	for (int i = 0; i < Q; i++) {
		Node ans = sgt.get(1, 0, N - 1, L[i], R[i]);
		int len = R[i] - L[i] + 1;
		C[i] = ans.sum + (len - ans.sum) * ans.mx;
	}
    return C;
}

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