QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#788485 | #9786. Magical Bags | ucup-team3519# | WA | 1ms | 3880kb | C++17 | 2.3kb | 2024-11-27 17:09:15 | 2024-11-27 17:09:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define V vector
#define pb push_back
#define fi first
#define se second
#define all0(x) (x).begin(), (x).end()
#define all1(x) (x).begin() + 1, (x).end()
typedef long long LL;
typedef pair<int, int> pi;
void solve(){
int n; cin >> n;
V<V<int>> a(n + 1);
for(int i = 1; i <= n; i++) {
int k; cin >> k;
a[i].resize(k);
for(int j = 0; j < k; j++) cin >> a[i][j];
sort(all0(a[i]));
}
V<int> l(n + 1), r(n + 1);
for(int i = 1; i <= n; i++) {
l[i] = *min_element(all0(a[i]));
r[i] = *max_element(all0(a[i]));
}
V<int> lmax(n + 1), rmin(n + 1);
V<int> ord(n + 1);
iota(all1(ord), 1);
set<int> st;
sort(all1(ord), [&](int x, int y) {
return l[x] < l[y];
});
for(int i = 1; i <= n; i++) {
int x = ord[i];
while(st.size() && *st.begin() < l[x]) st.erase(st.begin());
if(st.size()) {
rmin[x] = *st.begin();
} else {
rmin[x] = 2e9;
}
st.insert(r[x]);
}
st.clear();
sort(all1(ord), [&](int x, int y) {
return r[x] > r[y];
});
for(int i = 1; i <= n; i++) {
int x = ord[i];
while(st.size() && *st.rbegin() > r[x]) st.erase(st.begin());
if(st.size()) {
lmax[x] = *st.rbegin();
} else {
lmax[x] = 0;
}
st.insert(l[x]);
}
// for(int i = 1; i <= n; i++) cout << lmax[i] << " " << rmin[i] << "\n";
V<pi> item;
for(int i = 1; i <= n; i++) {
auto it = lower_bound(all0(a[i]), lmax[i]);
while(it != a[i].end() && *it <= rmin[i]) {
item.pb({*it, r[i]});
it++;
}
}
sort(all0(item));
item.pb({2e9, 0});
// for(auto [x, y] : item) cout << x << " " << y << "\n";
V<int> dp(item.size());
for(int i = 0; i + 1 < item.size(); i++) {
dp[i + 1] = max(dp[i], dp[i + 1]);
dp[lower_bound(all0(item), pi{item[i].se + 1, 0}) - item.begin()]
= max(dp[lower_bound(all0(item), pi{item[i].se + 1, 0}) - item.begin()], dp[i] + 1);
}
cout << 2 * n - dp.back() << "\n";
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
// int t; cin >> t;
// while(t--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
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: 3636kb
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: 3572kb
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: 3516kb
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: 3880kb
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:
172
result:
wrong answer 1st numbers differ - expected: '177', found: '172'