QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#785995#9786. Magical Bagsjaker#WA 3ms22228kbC++172.6kb2024-11-26 19:51:002024-11-26 19:51:01

Judging History

This is the latest submission verdict.

  • [2024-11-26 19:51:01]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 22228kb
  • [2024-11-26 19:51:00]
  • Submitted

answer

#pragma GCC optimize("Ofast")
#define DEBUG 0
#include <cstring>
#include <algorithm>
#include <queue>
#include <climits>
#include <cassert>
#include <iostream>
#include <vector>
#include <set>
template <class T> using Arr = std::vector<T>;
#define LS (p << 1)
#define RS (LS | 1)
#define MID ((l + r) >> 1)
typedef long long LL;

const int INF = 0x3F3F3F3F;
const int MAXN = 200005;
int n;
Arr<int> a[MAXN], b[MAXN];
int perm[MAXN];
int st[20][MAXN];
int nxt[MAXN];
int f[MAXN];

inline int ask(int l, int r) {
	if (l > r)
		return INF;
	int d = 1;
	while ((1 << (d + 1)) <= r - l + 1)
		++d;
	return std::min(st[d][l], st[d][r - (1 << d) + 1]);
}

inline void Upd(int &u, int v) {
	if (u > v)
		u = v;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin >> n;
	memset(f, 0x3F, sizeof(f));
	f[1] = 0;
	for (int i = 1; i <= n; ++i) {
		int K;
		std::cin >> K;
		b[i].resize(K);
		for (auto &x : b[i])
			std::cin >> x;
		std::sort(b[i].begin(), b[i].end());
		perm[i] = i;
	}
	std::sort(perm + 1, perm + n + 1, [&](int u, int v) {
			return b[u][0] < b[v][0];
		});
	for (int i = 1; i <= n; ++i)
		a[i] = b[perm[i]];

	nxt[n] = n + 1;
	for (int i = n; i >= 1; --i)
		if (a[i].size() == 1)
			nxt[i - 1] = i;
		else
			nxt[i - 1] = nxt[i];

	for (int i = 1; i <= n; ++i)
		st[0][i] = a[i][a[i].size() - 1];
	for (int j = 1; j < 20; ++j)
		for (int i = 1; i + (1 << j) - 1 <= n; ++i)
			st[j][i] = std::min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);

	std::set<int> s1;

	for (int i = 1; i <= n; ++i)
		if (a[i].size() == 1) {
			int p = std::upper_bound(a + 1, a + n + 1, a[i][0], [&](int x, Arr<int> &v) {
						return x < v[0];
					}) - a;
			int to = std::min(p, nxt[i]);
			Upd(f[to], f[i] + 1 + 2 * (to - i - 1));
		} else {
			auto p1 = s1.upper_bound(a[i][0]);
			int l1 = 0;
			if (p1 != s1.end())
				l1 = *p1;

			int last = a[i][a[i].size() - 1];
			int p = std::lower_bound(a + 1, a + n + 1, last, [&](Arr<int> &v, int x) {
					return v[0] < x;
					}) - a;
			assert(i < p);
			int l2 = a[p - 1][0] + 1;
			int l = std::max(l1, l2);
			// printf("(p l %d %d %d)\n", i, p, l);
			int r = ask(i + 1, p - 1) - 1;  // [l, r]

			auto lp = std::lower_bound(a[i].begin(), a[i].end(), l);
			auto rp = std::upper_bound(a[i].begin(), a[i].end(), r);
			int to = std::min(p, nxt[i]);
			if (lp < rp) {
				// printf("(= %d %lu %lu (to %d))\n", i, lp - a[i].begin(), rp - a[i].begin(), to);
				Upd(f[to], f[i] + 1 + 2 * (to - i - 1));
			}
			Upd(f[i + 1], f[i] + 2);
		}
	printf("%d\n", f[n + 1]);
	return 0;
}

详细

Test #1:

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

input:

4
3 4 7 10
2 1 9
4 11 2 8 14
3 6 12 13

output:

7

result:

ok 1 number(s): "7"

Test #2:

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

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

4
3 4 7 10
2 1 9
4 11 2 8 14
3 6 12 13

output:

7

result:

ok 1 number(s): "7"

Test #4:

score: 0
Accepted
time: 3ms
memory: 18388kb

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 22228kb

input:

100
4 372861091 407948190 424244630 359746969
6 568180757 527358812 494745349 665803213 674832670 586694351
4 696340797 775899164 919971335 716827187
4 123145962 344250363 122030550 251739234
4 342654413 368648894 150539766 255189030
1 194505887
3 755984448 736803561 745474041
4 709314938 498953418 ...

output:

176

result:

wrong answer 1st numbers differ - expected: '177', found: '176'