QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#786116#9786. Magical Bagsjaker#Compile Error//Rust2.8kb2024-11-26 20:22:442024-11-26 20:22:45

Judging History

This is the latest submission verdict.

  • [2024-11-26 20:22:45]
  • Judged
  • [2024-11-26 20:22:44]
  • 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 = INF;
			if (p1 != s1.end())
				l1 = *p1;
#if DEBUG
			printf("(%d (l1 %d))\n", i, l1);
#endif
			s1.insert(a[i][a[i].size() - 1]);

			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 = (p > i + 1 ? a[p - 1][0] + 1 : 0);
			// int l = std::max(l1, l2);
			int l = l2;
			int r = std::min(ask(i + 1, p - 1) - 1, l1);  // [l, r]
#if DEBUG
			printf("(%d (p %d) (l %d) (r %d))\n", i, p, l, r);
#endif

			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) {
#if DEBUG
				printf("(= %d %lu %lu (to %d))\n", i, lp - a[i].begin(), rp - a[i].begin(), to);
#endif
				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;
}

詳細信息

error: expected one of `!` or `[`, found `pragma`
 --> answer.code:1:2
  |
1 | #pragma GCC optimize("Ofast")
  |  ^^^^^^ expected one of `!` or `[`

error: aborting due to previous error