QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#786116 | #9786. Magical Bags | jaker# | Compile Error | / | / | Rust | 2.8kb | 2024-11-26 20:22:44 | 2024-11-26 20:22:45 |
Judging History
This is the latest submission verdict.
- [2024-11-26 20:22:45]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [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;
}
Details
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