QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#775220 | #9786. Magical Bags | ucup-team896# | WA | 2ms | 7792kb | C++20 | 2.1kb | 2024-11-23 15:04:32 | 2024-11-23 15:04:33 |
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 = 200010;
int n, m, sz, c[maxn], vis[maxn], mn[maxn];
pii a[maxn], b[maxn];
bool check(int x, int y) {
if (b[x].fi >= b[y].se) return false;
if (b[y].fi >= b[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);
}
sort(a + 1, a + n + 1);
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];
}
rep (i, 1, n) if (!vis[i]) b[++m] = a[i];
// rep (i, 1, m) cerr << b[i].fi << " " << b[i].se << '\n';
for (int l = 1, r; l <= m; l = r + 1) {
r = l;
while (r < m && b[r + 1].fi < b[l].se) r++;
if (l == r) {
ans += g(b[l]);
} 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) if (i != x && i != y) ans += g(b[i]);
if (check(x, y)) ans += g(b[x]) + g(b[y]) - min(1, g(b[x]) - 1 + g(b[y]) - 1);
else ans += g(b[x]) + g(b[y]) - min(1, g(b[x]) - 1) - min(1, g(b[y]) - 1);
}
}
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7792kb
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: 7660kb
input:
4 1 1 1 2 1 3 1 4
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 1ms
memory: 7784kb
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: 1ms
memory: 7784kb
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: 1ms
memory: 7792kb
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:
186
result:
wrong answer 1st numbers differ - expected: '177', found: '186'