Submission #1275302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275302		nicolo_010	Meetings (IOI18_meetings)	C++20	0 / 100	23 ms	2112 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct Node {
	int val, le, ri;
};

Node vd;
Node invalid;

struct DSU {
	vector<int> rank, parent;
	vector<int> left, right;
	DSU(int n) {
		rank.assign(n, 1);
		parent.resize(n);
		left.resize(n);
		right.resize(n);
		for (int i=0; i<n; i++) {
			parent[i] = i;
			left[i] = i;
			right[i] = i;
		}
	}

	int find(int n) {
		return (n == parent[n] ? n : parent[n] = find(parent[n]));
	}

	void unite(int n1, int n2) {
		int p1 = find(n1);
		int p2 = find(n2);
		if (rank[p1] >= rank[p2]) {
			rank[p1] += rank[p2];
			parent[p2] = p1;
			left[p1] = min(left[p1], left[p2]);
			right[p1] = max(right[p1], right[p2]);
		}
		else {
			rank[p2] += rank[p1];
			parent[p1] = p2;
			right[p2] = max(right[p1], right[p2]);
			left[p2] = min(left[p1], left[p2]);
		}
	}
};

struct SegTree {
	vector<Node> tree;
	SegTree(int n) {
		tree.assign(4*n, vd);
	}

	void query(int p, int l, int r, int i, int x, int lee, int rii) {
		if (l > i || r < i) return;
		if (l==r && r==i) {
			tree[p].val = x;
			tree[p].le = lee;
			tree[p].ri = rii;
		}
		else {
			int m = (l+r)/2;
			query(2*p, l, m, i, x, lee, rii);
			query(2*p+1, m+1, r, i, x, lee, rii);
			Node i1 = tree[2*p];
			Node i2 = tree[2*p+1];
			if (i1.val > i2.val) {
				tree[p].val = i1.val;
				tree[p].le = i1.le;
				tree[p].ri = i1.ri;
			}
			else {
				tree[p].val = i2.val;
				tree[p].le = i2.le;
				tree[p].ri = i2.ri;
			}
		}
	}

	Node rmq(int p, int l, int r, int i, int j) {
		if (i > j) return invalid;
		if (l > j || r < i) return invalid;
		if (i <= l && r <= j) {
			return tree[p];
		}
		else {
			int m = (l+r)/2;
			Node i1 = rmq(2*p, l, m, i, j);
			Node i2 = rmq(2*p+1, m+1, r, i, j);
			if (i1.val == -1) return i2;
			if (i2.val == -1) return i1;
			if (i1.val > i2.val) {
				return i2;
			}
			else {
				return i1;
			}
		}
	}
};

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	vd.val = 0;
	vd.le = 0;
	vd.ri = 0;
	invalid.val = -1;
	int N = H.size();
	int Q = L.size();
	vector<int> a(N);
	vector<pii> segm(N);
	DSU dsu(N);
	SegTree st(N);
	for(int i=0; i<N-1; i++) {
		if (H[i] == H[i+1] && H[i] == 1) {
			dsu.unite(i, i+1);
		}
	}
	for (int i=0; i<N; i++) {
		if (H[i] == 2) dsu.rank[i] = 0;
	}
	for (int i=0; i<N; i++) {
		int p = dsu.find(i);
		a[i] = dsu.rank[p];
		segm[i].first = dsu.left[p];
		segm[i].second = dsu.right[p];
	}
	for (int i=0; i<N; i++) {
		st.query(1, 0, N-1, i, a[i], segm[i].first, segm[i].second);
	}
	vector<ll> ans(Q);
	for (int i=0; i<Q; i++) {
		int caso1, caso2, caso3;
		caso1 = caso2 = caso3 = 0;
		Node i1 = st.rmq(1, 0, N-1, L[i], R[i]);
		int l = i1.le;
		int r = i1.ri;
		caso1 = i1.val;
		if (r >= R[i] && l <= L[i] && i1.val != 0)  {
			ans[i] = R[i]-L[i]+1;
			continue;
		}
		if (l < L[i]) {
			l = L[i];
			caso1 = (r-l+1);
			Node i2 = st.rmq(1, 0, N-1, r+1, R[i]);
			int lee = i2.le;
			int ree = i2.ri;
			caso2 = i2.val;
			if (ree > R[i]) {
				ree = R[i];
				caso2 = (ree-lee+1);
				Node i3 = (st.rmq(1, 0, N-1, r+1, lee-1));
				caso3 = i3.val;
			}
		}
		if (r > R[i]) {
			r = R[i];
			caso1 = (r-l+1);
			Node i2 = st.rmq(1, 0, N-1, L[i], l-1);
			int lee = i2.le;
			int ree = i2.ri;
			caso2 = i2.val;
			if (lee < L[i]) {
				lee = L[i];
				caso2 = (ree-lee+1);
				Node i3 = st.rmq(1, 0, N-1, ree+1, l-1);
				caso3 = i3.val;
			}
		}
		int mx = max({
			caso1, caso2, caso3
		});
		ans[i] = 2*(R[i]-L[i]+1) - mx;
	}
	return ans;
}

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