QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#487990#6633. Exam Requirementsucup-team052#ML 15ms14060kbC++232.9kb2024-07-23 14:34:512024-07-23 14:34:53

Judging History

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

  • [2024-07-23 14:34:53]
  • 评测
  • 测评结果:ML
  • 用时:15ms
  • 内存:14060kb
  • [2024-07-23 14:34:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, M = 2e7;

vector <int> adj[M];
int l[N], r[N], b[N];
int T, n, m, tot, len;

inline void adde(int u, int v) {
	if (u && v) {
		adj[u].push_back(v);
		// fprintf(stderr, "u = %d, v = %d\n", u, v);
	}
}

int p1[N << 2], p2[N << 2];
int ID;
void query(int u, int L, int R, int l, int r) {
	// fprintf(stderr, "u = %d, L = %d, R = %d, l = %d, r = %d\n", u, L, R, l, r);
	if (l <= L && R <= r) {
		adde(ID * 2, p1[u]); adde(p2[u], ID * 2 - 1);
		++tot;
		adde(tot * 2 - 1, p1[u]);
		if (L != R) {
			adde(tot * 2 - 1, p1[u << 1]);
			adde(tot * 2 - 1, p1[u << 1 | 1]);
		}
		p1[u] = tot * 2 - 1;
		adde(p2[u], tot * 2);
		if (L != R) {
			adde(p2[u << 1], tot * 2);
			adde(p2[u << 1 | 1], tot * 2);
		}
		p2[u] = tot * 2;
		adde(p1[u], ID * 2 - 1);
		adde(ID * 2, p2[u]);
		return;
	}
	int mid = (L + R) >> 1;
	if (mid >= l) query(u << 1, L, mid, l, r);
	if (mid + 1 <= r) query(u << 1 | 1, mid + 1, R, l, r);
	++tot;
	adde(tot * 2 - 1, p1[u]);
	adde(tot * 2 - 1, p1[u << 1]);
	adde(tot * 2 - 1, p1[u << 1 | 1]);
	p1[u] = tot * 2 - 1;
	adde(p2[u], tot * 2);
	adde(p2[u << 1], tot * 2);
	adde(p2[u << 1 | 1], tot * 2);
	p2[u] = tot * 2;
}

int low[M], dfn[M], st[M], col[N * 2];
bool inst[M];
int dfnt, top, cnt;
void tarjan(int u) {
	low[u] = dfn[u] = ++dfnt; st[++top] = u; inst[u] = 1;
	for (auto v : adj[u]) {
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if (inst[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (low[u] == dfn[u]) {
		++cnt;
		int tmp = 0;
		while (tmp != u) {
			tmp = st[top--];
			inst[tmp] = 0;
			if (tmp <= 2 * n) col[tmp] = cnt;
		}
	}
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++) {
			scanf("%d%d", &l[i], &r[i]);
			b[i] = l[i];
		}
		for (int i = 1; i <= m; i++) {
			int a, b;
			scanf("%d%d", &a, &b);
			adde(a * 2 - 1, b * 2);
			adde(b * 2 - 1, a * 2);
		}
		sort(b + 1, b + n + 1);
		len = unique(b + 1, b + n + 1) - b - 1;
		for (int i = 1; i <= n; i++) {
			l[i] = lower_bound(b + 1, b + len + 1, l[i]) - b;
			r[i] = upper_bound(b + 1, b + len + 1, r[i]) - b - 1;
		}
		tot = n;
		for (int i = 1; i <= len * 4; i++) p1[i] = p2[i] = 0;
		for (int i = 1; i <= n; i++) {
			ID = i;
			query(1, 1, len, l[i], r[i]);
			// add(1, 1, len, l[i], r[i]);
		}
		for (int i = 1; i <= len * 4; i++) p1[i] = p2[i] = 0;
		for (int i = n; i >= 1; i--) {
			ID = i;
			query(1, 1, len, l[i], r[i]);
			// add(1, 1, len, l[i], r[i]);
		}
		dfnt = cnt = 0;
		for (int i = 1; i <= n * 2; i++) {
			if (!dfn[i]) {
				tarjan(i);
			}
		}
		int ans = 1;
		for (int i = 1; i <= n; i++) {
			if (col[i * 2 - 1] == col[i * 2]) {
				ans = 0;
				break;
			}
		}
		printf("%s\n", ans ? "YES" : "NO");
		for (int i = 1; i <= tot * 2; i++) adj[i].clear(), dfn[i] = 0;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 15ms
memory: 14060kb

input:

2
3 1
1 5
2 7
10 11
2 1
3 3
1 5
2 7
5 7
1 2
2 3
3 1

output:

YES
NO

result:

ok 2 lines

Test #2:

score: -100
Memory Limit Exceeded

input:

1
100000 100000
15084647 15220430
217541056 217598054
222963701 223110976
71224450 71340221
320463268 320631387
334861459 334924668
328950591 329083669
178996498 178996584
428529461 428605033
405428435 405504132
197936687 197947412
9058562 9190197
169407597 169474101
297518153 297590927
31471874 316...

output:

NO

result: