QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#801719 | #9786. Magical Bags | ucup-team1430# | WA | 0ms | 3832kb | C++20 | 1.6kb | 2024-12-07 06:35:24 | 2024-12-07 06:35:25 |
Judging History
answer
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define pb push_back
#define eb emplace_back
#define debug(x) cout << #x << ": " << x << endl
// #define debug(...)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)((x).size())
#define esp ' '
#define pii pair<int,int>
#define vi vector<int>
typedef long long ll;
const int oo = 1e9+1;
using namespace std;
void solve() {
int n; cin >> n;
vector<pair<int, int>> rgs(n);
vector<int> ls(n), rs(n);
int ans = 0;
int sum = 0;
rep(i, 0, n) {
int k; cin >> k;
sum += k;
int minv = oo;
int maxv = -oo;
rep(j, 0, k) {
int x; cin >> x;
minv = min(minv, x);
maxv = max(maxv, x);
}
ans += k -2;
if (minv == maxv) ans++;
rgs[i] = {minv, maxv};
ls[i] = minv;
rs[i] = maxv;
}
sort(all(rgs));
sort(all(ls));
sort(all(rs));
auto query = [&](int l, int r, const vector<int> & v) {
int bigr = lower_bound(all(v), r) - v.begin();
int small = upper_bound(all(v), l) - v.begin();
return max(bigr - small, 0);
};
vector<int> dp(n+1, 0);
dp[n] = 0;
for (int i = n-1; i >= 0; i--) {
int nxt = upper_bound(all(rgs), pair{rgs[i].second +1, (int)-1}) - rgs.begin();
dp[i] = dp[i+1];
if (rgs[i].first == rgs[i].second) continue;
if (query(rgs[i].first, rgs[i].second, ls) == 0) {
dp[i] = max(dp[i], 1 + dp[nxt]);
}
if (query(rgs[i].first, rgs[i].second, rs) == 0) {
dp[i] = max(dp[i], 1 + dp[nxt]);
}
}
// debug(ans);
// debug(dp[0]);
cout << sum - (dp[0] + ans) << endl;
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
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: 3832kb
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: 3580kb
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: 3656kb
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: 3640kb
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'