CF377D Developing Game

题目链接：

题目分析：

把每个人当成一个三元组\([l_i, r_i, v_i]\)

考虑每个人对哪个能力区间\([L, R]\)有贡献

应该是左端点在\([l_i, v_i]\)，右端点在\([v_i, r_i]\)的区间

拍到一个二维平面上，求最多有多少个矩形交一起

线段树维护扫描线即可

代码：

#include<bits/stdc++.h>

#define N (600000 + 10)

using namespace std;

inline int read() {

	int cnt = 0, f = 1; char c = getchar();

	while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}

	while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + (c ^ 48); c = getchar();}

	return cnt * f;

}

int n, Y[N], cnt, ans = 0, ansx, ansy, tot;

int l[N], r[N], v[N];

struct node2 {

	int x, Y1, Y2, tag;

}seg[N << 1];

struct node {

	int l, r;

	int tag, gmax, pos;

	#define l(p) tree[p].l

	#define r(p) tree[p].r

	#define tag(p) tree[p].tag

	#define gmax(p) tree[p].gmax

	#define pos(p) tree[p].pos

} tree[N << 2];

void pushdown(int p) {

	tag(p << 1) += tag(p);

	tag(p << 1 | 1) += tag(p);

	gmax(p << 1) += tag(p);

	gmax(p << 1 | 1) += tag(p);

	tag(p) = 0;

}

void pushup(int p) {

	if (gmax(p << 1) > gmax(p << 1 | 1)) {

		pos(p) = pos(p << 1);

		gmax(p) = gmax(p << 1);

	} else {

		pos(p) = pos(p << 1 | 1);

		gmax(p) = gmax(p << 1 | 1);

	}

}

void build (int p, int l, int r) {

	l(p) = l, r(p) = r;

	if (l == r) {pos(p) = Y[l]; return;}

	int mid = (l + r) >> 1;

	build (p << 1, l, mid);

	build (p << 1 | 1, mid + 1, r);

	pos(p) = pos(p << 1);

}

void modify(int p, int l, int r, int k) {

	pushdown(p);

	if (l <= Y[l(p)] && r >= Y[r(p)]) {tag(p) += k, gmax(p) += k; return;}

	int mid = (l(p) + r(p)) >> 1;

	if (l <= Y[mid]) modify(p << 1, l, r, k);

	if (r > Y[mid]) modify(p << 1 | 1, l, r, k);

	pushup(p);

}

bool cmp(node2 a, node2 b) {

	return a.x == b.x ? a.tag > b.tag : a.x < b.x;

}

int main() {

// 	freopen("data.in", "r", stdin);

// 	freopen("myself.out", "w", stdout);

	n = read();

	for (register int i = 1; i <= n; ++i) {

		l[i] = read(), v[i] = read(), r[i] = read();

		seg[++tot].x = l[i], seg[tot].Y1 = v[i], seg[tot].Y2 = r[i], seg[tot].tag = 1, Y[tot] = v[i];

		seg[++tot].x = v[i], seg[tot].Y1 = v[i], seg[tot].Y2 = r[i], seg[tot].tag = -1, Y[tot] = r[i];

	}

	sort (Y + 1, Y + tot + 1);

	for (register int i = 1; i <= tot; ++i) if (Y[i] != Y[i + 1]) Y[++cnt] = Y[i];

	build (1, 1, cnt);

	sort (seg + 1, seg + tot + 1, cmp);

//	for (register int i = 1; i <= cnt; ++i) cout<<Y[i]<<" "; return 0;

	for (register int i = 1; i <= tot; ++i) {

		modify(1, seg[i].Y1, seg[i].Y2, seg[i].tag);

//		cout<<gmax(1)<<" ";

		if (gmax(1) > ans) {

			ans = gmax(1);

			ansx = seg[i].x;

			ansy = pos(1);

		}

	}

//	return 0;

	printf("%d\n", ans);

//	cout<<ansx<<" "<<ansy<<endl; return 0;

	for (register int i = 1; i <= n; ++i)

		if (v[i] <= ansy && r[i] >= ansy && l[i] <= ansx && v[i] >= ansx) printf("%d ", i);

	return 0;

}

巴特西

CF377D Developing Game

题目链接：

题目分析：

代码：

最新文章

热门文章