QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423104#8179. 2D ParenthesescomplexorWA 2ms11856kbC++232.8kb2024-05-27 21:07:322024-05-27 21:07:33

Judging History

你现在查看的是最新测评结果

  • [2024-05-27 21:07:33]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11856kb
  • [2024-05-27 21:07:32]
  • 提交

answer

#include <bits/stdc++.h>
typedef long long LL;
#define clr(a, n) memset(a, 0, sizeof(int) * (n))
#define cpy(a, b, n) memcpy(a, b, sizeof(int) * (n))
int read()
{
	int s = 0, f = 1;
	char c = getchar();
	while (!(c >= '0' && c <= '9'))
		f ^= (c == '-'), c = getchar();
	while (c >= '0' && c <= '9')
		s = s * 10 + (c ^ 48), c = getchar();
	return f ? s : -s;
}
const int MAXN = 400005;
struct Point 
{ 
	int x, y, id, o; 
	friend bool operator<(Point a, Point b){ return a.x != b.x ? a.x < b.x : a.y < b.y; }
} p[MAXN << 1];
struct Segment
{
	int x, yl, yr, v;
	Segment(){}
	Segment(int _x, int _yl, int _yr, int _v)
	: x(_x), yl(_yl), yr(_yr), v(_v) {}
} sg[MAXN << 1];
std::set<Point> rec;
int n, ans[MAXN], m = 0, yy[MAXN << 1], V;
namespace BIT
{
	int c[MAXN << 1] = {0};
	void modify(int x, int v)
	{
		for (; x <= V; x += x & -x)
			c[x] += v;
	}
	int query(int x)
	{
		int res = 0;
		for (; x; x -= x & -x)
			res += c[x];
		return res;
	}
	int query(int l, int r) { return query(r) - query(l - 1); }
}
int getId(int y){ return std::lower_bound(yy + 1, yy + V + 1, y) - yy; }
int main() 
{
	n = read();
	for (int i = 1; i <= n; i++)
		p[i].x = read(), p[i].y = read(), p[i].id = i, p[i].o = 0;
	for (int i = 1 + n; i <= n + n; i++)
		p[i].x = read(), p[i].y = read(), p[i].id = i - n, p[i].o = 1;
	if (n <= 2) return printf("NO"), 0;
	std::sort(p + 1, p + n * 2 + 1, [](Point a, Point b){ return a.y != b.y ? a.y < b.y : a.x > b.x; });
	for (int i = 1; i <= n * 2; i++)
	{
		// printf("%d %d %d %d\n", p[i].x, p[i].y, p[i].id, p[i].o);
		// if (i == 4) for (Point t : rec) printf("%d %d %d %d\n", t.x, t.y, t.id, t.o);
		yy[i] = p[i].y;
		if (p[i].o == 0) rec.insert(p[i]);
		else
		{
			auto it = rec.lower_bound(Point(p[i].x - 1, -1e9 - 1, 0, 0));
			if (it == rec.begin()) return printf("No\n"), 0;
			// printf("!%d\n", it->id);
			--it, ans[it->id] = p[i].id;
			// printf("%d: %d\n", i, it->id);
			sg[++m] = Segment(it->x, it->y, p[i].y, 1);
			sg[++m] = Segment(p[i].x, it->y, p[i].y, -1);
			rec.erase(it);
		}
	}
	V = std::unique(yy + 1, yy + n * 2 + 1) - yy - 1;
	std::sort(sg + 1, sg + m + 1, [](Segment a, Segment b){
		if (a.x == b.x && a.v == b.v)
			return a.v == -1 ? a.yr - a.yl < b.yr - b.yl : a.yr - a.yl > b.yr - b.yl;
		return a.x == b.x ? a.v < b.v : a.x < b.x;
	});
	for (int i = 1; i <= m; i++)
	{
		int l = getId(sg[i].yl), r = getId(sg[i].yr);
		// printf("%d: %d %d %d %d %d\n", i, sg[i].x, sg[i].yl, sg[i].yr, sg[i].v, BIT::query(l + 1, r - 1));
		if (sg[i].v == 1 && l < r && BIT::query(l + 1, r - 1) > 0) ;
			// return printf("No"), 0;
		if (sg[i].v == -1 && l < r && BIT::query(l + 1, r - 1) > 0) ;
			// return printf("No\n"), 0;
		BIT::modify(l, sg[i].v), BIT::modify(r, sg[i].v);
	}
	printf("Yes\n");
	for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 11856kb

input:

3
0 0
2 -2
1 1
2 2
3 1
2 3

output:

No

result:

wrong answer expected YES, found NO