QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#786122 | #9786. Magical Bags | jaker# | WA | 3ms | 10756kb | C++20 | 2.8kb | 2024-11-26 20:23:18 | 2024-11-26 20:23:19 |
Judging History
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
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 10756kb
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: 2ms
memory: 8572kb
input:
4 1 1 1 2 1 3 1 4
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 2ms
memory: 8868kb
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: 0ms
memory: 8200kb
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: 10744kb
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:
178
result:
wrong answer 1st numbers differ - expected: '177', found: '178'