QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423254#8179. 2D ParenthesescomplexorWA 126ms18240kbC++233.9kb2024-05-27 21:52:372024-05-27 21:52:39

Judging History

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

  • [2024-05-27 21:52:39]
  • 评测
  • 测评结果:WA
  • 用时:126ms
  • 内存:18240kb
  • [2024-05-27 21:52:37]
  • 提交

answer

#include <bits/stdc++.h>
typedef long long LL;
typedef std::pair<int, int> pii;
#define MP std::make_pair
#define fi first
#define se second
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 Tuple 
{ 
	int x, y, z; 
	Tuple(int _x = 0, int _y = 0, int _z = 0)
	: x(_x), y(_y), z(_z){}
	friend bool operator<(Tuple t1, Tuple t2)
	{ return t1.x != t2.x ? t1.x < t2.x : t1.y != t2.y ? t1.y < t2.y : t1.z < t2.z; }
} ;
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<Tuple> rec;
int n, ans[MAXN], m = 0, yy[MAXN << 1], V;
int ida[MAXN], idb[MAXN];
pii a[MAXN], b[MAXN];
namespace SGT
{
	#define ls (x << 1)
	#define rs (x << 1 | 1)
	int mx[MAXN << 3], mn[MAXN << 3], lzy[MAXN << 3];
	void hard(int x, int v){ mx[x] += v, mn[x] += v, lzy[x] += v; }
	void spread(int x){ if (lzy[x]) hard(ls, lzy[x]), hard(rs, lzy[x]), lzy[x] = 0; }
	void modify(int x, int l, int r, int ql, int qr, int v)
	{
		if (ql <= l && r <= qr) return hard(x, v);
		int mid = (l + r) >> 1; spread(x);
		if (ql <= mid) modify(ls, l, mid, ql, qr, v);
		if (qr > mid) modify(rs, mid + 1, r, ql, qr, v);
		mn[x] = std::min(mn[ls], mn[rs]);
		mx[x] = std::max(mx[ls], mx[rs]);
	}
	pii query(int x, int l, int r, int ql, int qr)
	{
		if (ql <= l && r <= qr) return MP(mn[x], mx[x]);
		int mid = (l + r) >> 1; pii res(1e9, -1e9); spread(x);
		if (ql <= mid) 
		{
			pii q = query(ls, l, mid, ql, qr);
			res.fi = std::min(res.fi, q.fi);
			res.se = std::max(res.se, q.se);
		}
		if (qr > mid) 
		{
			pii q = query(rs, mid + 1, r, ql, qr);
			res.fi = std::min(res.fi, q.fi);
			res.se = std::max(res.se, q.se);
		}
		return res;
	}
}
int getId(int y){ return std::lower_bound(yy + 1, yy + V + 1, y) - yy; }
std::multiset<int> ms;
int main() 
{
	n = read();
	for (int i = 1; i <= n; i++) a[i].fi = read(), a[i].se = read();
	for (int i = 1; i <= n; i++) b[i].fi = read(), b[i].se = read();
	std::iota(ida + 1, ida + n + 1, 1);
	std::iota(idb + 1, idb + n + 1, 1);
	std::sort(ida + 1, ida + n + 1, [](int i, int j){ return a[i] > a[j]; });
	std::sort(idb + 1, idb + n + 1, [](int i, int j){ return b[i] > b[j]; });
	for (int i = 1, j = 1; i <= n; i++)
	{
		for (; j <= n && b[idb[j]].fi > a[ida[i]].fi; j++)
			rec.emplace(b[idb[j]].se, b[idb[j]].fi, idb[j]);
		auto it = rec.lower_bound(Tuple(a[ida[i]].se + 1, -1e9 - 1, 0));
		if (it == rec.end()) return printf("No\n"), 0;
		ans[ida[i]] = it->z, rec.erase(it);
	}
	std::iota(ida + 1, ida + n + 1, 1);
	std::iota(idb + 1, idb + n + 1, 1);
	std::sort(ida + 1, ida + n + 1, [](int i, int j){ return a[i].fi < a[j].fi; });
	std::sort(idb + 1, idb + n + 1, [](int i, int j){ return b[ans[i]].fi < b[ans[j]].fi; });
	for (int i = 1, j = 1, k = 1; i <= n; i++)
	{
		for (; j <= n && a[ida[j]].fi < a[ida[i]].fi; j++) 
			ms.insert(a[ida[j]].se), ms.insert(b[ans[ida[j]]].se);
		for (; k <= n && b[idb[k]].fi <= a[ida[i]].fi; k++) 
			ms.erase(ms.find(a[idb[k]].se)), ms.erase(ms.find(b[ans[idb[k]]].se));
		auto it = ms.upper_bound(a[ida[i]].se);
		if (it != ms.end() && *it < b[ans[ida[i]]].se) return printf("No"), 0;
	}
	ms.clear();
	for (int i = 1, j = 1, k = 1; i <= n; i++)
	{
		for (; j <= n && a[ida[j]].fi < b[ans[idb[i]]].fi; j++) 
			ms.insert(a[ida[j]].se), ms.insert(b[ans[ida[j]]].se);
		for (; k <= n && b[idb[k]].fi <= b[ans[idb[i]]].fi; k++) 
			ms.erase(ms.find(a[idb[k]].se)), ms.erase(ms.find(b[ans[idb[k]]].se));
		auto it = ms.upper_bound(a[idb[i]].se);
		if (it != ms.end() && *it < b[ans[idb[i]]].se) return printf("No"), 0;
	}
	printf("Yes\n");
	for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 16160kb

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: 2ms
memory: 16036kb

input:

2
1 0
0 1
2 3
3 2

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 0ms
memory: 11984kb

input:

1
1 1
0 0

output:

No

result:

ok answer is NO

Test #4:

score: -100
Wrong Answer
time: 126ms
memory: 18240kb

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:

No

result:

wrong answer expected YES, found NO