QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#385557#6308. MagicZZZWA 5ms6220kbC++232.6kb2024-04-10 21:12:452024-04-10 21:12:46

Judging History

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

  • [2024-04-10 21:12:46]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:6220kb
  • [2024-04-10 21:12:45]
  • 提交

answer

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define MP make_pair
#define ep emplace
#define eb emplace_back
//#define int long long
#define rep(i, j, k) for (int i = j; i <= k; i++)
#define per(i, j, k) for (int i = j; i >= k; i--)
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef __int128 lll;
typedef unsigned long long ull;
typedef unsigned int ui;
using namespace std;

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 - '0', c = getchar();
	return f ? s : -s;
}
const int inf = 0x3f3f3f3f;
int n, s, t, tot = 1, head[200005], dis[200005], now[200005], rt, cnt;
struct edge { int to, nxt, flow; } e[200005];
void addedge(int u, int v, int w) {
	e[++tot] = edge{ v, head[u], w }; head[u] = tot;
	e[++tot] = edge{ u, head[v], 0 }; head[v] = tot;
}
bool bfs() {
	memset(dis, 0x3f, sizeof dis);
	memcpy(now, head, sizeof now);
	queue<int> q;
	dis[s] = 0, q.ep(s);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to, w = e[i].flow;
			if (dis[v] != inf || !w) continue;
			dis[v] = dis[u] + 1;
			q.ep(v);
		}
	}
	return dis[t] != inf;
}
int dfs(int u, int sum) {
	if (u == t) return sum;
	int res = 0;
	for (int i = now[u]; i && sum; i = e[i].nxt) {
		int v = e[i].to, w = e[i].flow;
		if (dis[v] != dis[u] + 1 || !w) continue;
		int k = dfs(v, min(sum, w));
		e[i].flow -= k, e[i ^ 1].flow += k;
		sum -= k, res += k;
		if (!k) dis[v] = inf;
	}
	return res;
}
pii p[5005];
struct SGT {
	int ls[200005], rs[200005];
	void update(int l, int r, int pos, int u) {
		if (l == r) return addedge(u, t, 1);
		int mid = (l + r) >> 1;
		if (mid >= pos) {
			if (!ls[u]) addedge(u, ls[u] = ++cnt, inf);
			update(l, mid, pos, ls[u]);
		} else {
			if (!rs[u]) addedge(u, rs[u] = ++cnt, inf);
			update(mid + 1, r, pos, rs[u]);
		}
	}
	void query(int l, int r, int L, int R, int v, int u) {
		if (!u) return ;
		if (L <= l && r <= R) return addedge(v, u, 1);
		int mid = (l + r) >> 1;
		if (mid >= L) query(l, mid, L, R, v, ls[u]);
		if (mid < R) query(mid + 1, r, L, R, v, rs[u]);
	}
} sgt;

signed main() {
	n = read();
	rep(i, 1, n) p[i].fi = read(), p[i].se = read();
	s = 1, t = s + 1, rt = t + 1, cnt = rt + 1;
	sort(p + 1, p + n + 1);
	rep(i, 1, n) {
		addedge(s, ++cnt, 1);
		sgt.query(1, n + n, p[i].fi + 1, p[i].se - 1, cnt, rt);
		sgt.update(1, n + n, p[i].se, rt);
	}
	int ans = n + n;
	while (bfs()) ans -= dfs(s, inf);
	printf("%d\n", ans);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5384kb

input:

5
2 3
6 7
1 9
5 10
4 8

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: -100
Wrong Answer
time: 5ms
memory: 6220kb

input:

5000
7985 7987
42 46
1591 1593
407 410
6305 6306
1456 1457
5874 5875
7135 7137
7041 7046
6813 6815
8868 8871
665 666
4055 4056
9789 9796
7067 7068
4745 4746
5167 5171
1735 1737
2125 2128
1444 1447
1348 1352
6087 6090
1381 1384
1600 1601
5187 5190
2801 2802
8449 8450
9376 9377
4021 4024
2674 2676
490...

output:

8012

result:

wrong answer 1st numbers differ - expected: '8134', found: '8012'