QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#788485#9786. Magical Bagsucup-team3519#WA 1ms3880kbC++172.3kb2024-11-27 17:09:152024-11-27 17:09:15

Judging History

你现在查看的是最新测评结果

  • [2024-11-27 17:09:15]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3880kb
  • [2024-11-27 17:09:15]
  • 提交

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'