QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423107#8179. 2D ParenthesescomplexorWA 197ms27412kbC++232.8kb2024-05-27 21:08:202024-05-27 21:08:21

Judging History

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

  • [2024-05-27 21:08:21]
  • 评测
  • 测评结果:WA
  • 用时:197ms
  • 内存:27412kb
  • [2024-05-27 21:08:20]
  • 提交

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: 100
Accepted
time: 2ms
memory: 9944kb

input:

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

output:

Yes
3
2
1

result:

ok answer is YES, 3 tokens

Test #2:

score: 0
Accepted
time: 1ms
memory: 7800kb

input:

2
1 0
0 1
2 3
3 2

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 1ms
memory: 7940kb

input:

1
1 1
0 0

output:

NO

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 197ms
memory: 27412kb

input:

199996
94702923 895749121
-830347683 823853414
-638337012 -528381915
774504965 -903560893
465975432 931026841
47062323 901390864
539345338 830099354
278774201 896803047
-445303873 568413124
80473317 828648317
804283391 -307873779
543648687 893783688
814084625 -664894626
169476937 -999435847
-8232728...

output:

Yes
21701
88398
163202
52754
29196
93486
2981
198023
157367
48765
123135
18491
80650
112519
196489
109656
173973
5551
113259
136548
133688
182366
59175
165032
163355
93530
5843
31857
130090
155862
76890
97333
133685
85853
167272
4006
27179
1988
107334
29064
65560
70618
115785
151179
183975
13637
114...

result:

wrong answer 3rd words differ - expected: '59327', found: '163202'