QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#775501 | #9786. Magical Bags | ucup-team896# | WA | 2ms | 15924kb | C++20 | 3.4kb | 2024-11-23 16:06:05 | 2024-11-23 16:06:07 |
Judging History
answer
// Author: Klay Thompson
// Problem: F. Magical Bags
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }
using namespace std;
const int maxn = 500010;
int n, m, sz, c[maxn], vis[maxn], mn[maxn], d[maxn], tot;
int mnp[maxn], mxp[maxn];
pii a[maxn], b[maxn];
// map<int, int> mnp, mxp;
map<pii, int> cnt;
bool check(pii x, pii y) {
if (x.fi >= y.se) return false;
if (y.fi >= x.se) return false;
return true;
}
int g(pii x) {
return x.fi == x.se ? 1 : 2;
}
int main() {
cin.tie(nullptr) -> ios::sync_with_stdio(false);
cin >> n;
rep (i, 1, n) {
cin >> sz;
rep (j, 1, sz) cin >> c[j];
a[i].fi = *min_element(c + 1, c + sz + 1);
a[i].se = *max_element(c + 1, c + sz + 1);
d[++tot] = a[i].fi, d[++tot] = a[i].se;
}
sort(d + 1, d + tot + 1), tot = unique(d + 1, d + tot + 1) - d - 1;
rep (i, 1, n) a[i].fi = lower_bound(d + 1, d + tot + 1, a[i].fi) - d;
rep (i, 1, n) a[i].se = lower_bound(d + 1, d + tot + 1, a[i].se) - d;
rep (i, 1, n) cnt[a[i]]++;
sort(a + 1, a + n + 1);
rep (i, 0, tot + 1) mnp[i] = 1e9, mxp[i] = 0;
mn[n + 1] = 1e9;
per (i, n, 1) mn[i] = min(mn[i + 1], a[i].se);
int pos = 1, ans = 0;
rep (i, 1, n) {
while (pos <= n && a[pos].fi <= a[i].fi) pos++;
vis[i] = (mn[pos] < a[i].se), ans += 2 * vis[i];
if (vis[i]) {
chkmn(mnp[a[i].fi], a[i].fi);
chkmx(mxp[a[i].se], a[i].se);
// if (!mnp.count(a[i].se)) mnp[a[i].se] = 1;
// if (!mxp.count(a[i].fi)) mxp[a[i].fi] = 1;
}
}
per (i, tot, 1) chkmn(mnp[i], mnp[i + 1]);
rep (i, 1, tot) chkmx(mxp[i], mxp[i - 1]);
rep (i, 1, n) if (!vis[i]) b[++m] = a[i];
for (int l = 1, r; l <= m; l = r + 1) {
r = l;
while (r < m && b[r + 1].fi < b[r].se) r++;
// rep (i, l, r) cerr << b[i].fi << " " << b[i].se << '\n';
// cerr << "----\n";
if (l == r) {
if (b[l].fi == b[l].se) ans += 1;
else if (b[l].se <= mnp[b[l].fi] || b[l].fi >= mxp[b[l].se]) ans += 1;
else ans += 2;
} else {
int x = l, y = r;
rep (i, l, r) if (b[i].fi == b[l].fi && b[i].se < b[x].se) x = i;
rep (i, l, r) if (b[i].se == b[r].se && b[i].fi > b[y].fi) y = i;
rep (i, l, r) ans += g(b[i]);
int canx = b[x].fi >= mxp[b[x].se], cany = b[y].se <= mnp[b[y].fi];
// cerr << canx << " " << cany << endl;
if (cnt[b[x]] >= 2) canx = 0;
if (cnt[b[y]] >= 2) cany = 0;
rep (i, l, r) if (i != x && i != y) canx &= (check(b[x], b[i]) == check(pii(b[x].se, b[x].se), b[i]));
rep (i, l, r) if (i != x && i != y) cany &= (check(b[y], b[i]) == check(pii(b[y].fi, b[y].fi), b[i]));
if (check(b[x], b[y])) {
if (canx && check(pii(b[x].se, b[x].se), b[y])) ans--;
else if (cany && check(b[x], pii(b[y].fi, b[y].fi))) ans--;
} else {
ans -= canx + cany;
}
}
}
cout << ans << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 13808kb
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: 13868kb
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: 15924kb
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: 13872kb
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: 13968kb
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'