QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#798235#9786. Magical BagsvwxyzTL 1ms4028kbC++234.1kb2024-12-04 09:56:392024-12-04 09:56:40

Judging History

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

  • [2024-12-04 09:56:40]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4028kb
  • [2024-12-04 09:56:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

class SegmentTree {
    using F = function<pair<vector<int>, vector<int>>(pair<vector<int>, vector<int>>, pair<vector<int>, vector<int>>)>;
    int n, le;
    vector<pair<vector<int>, vector<int>>> seg;
    F func;
    pair<vector<int>, vector<int>> identity;

public:
    SegmentTree(int n, F func, pair<vector<int>, vector<int>> identity)
        : n(n), func(func), identity(identity) {
        le = 1;
        while (le < n) le *= 2;
        seg.assign(2 * le, identity);
    }

    void set(int i, pair<vector<int>, vector<int>> x) {
        i += le;
        seg[i] = x;
        while (i > 1) {
            i /= 2;
            seg[i] = func(seg[i * 2], seg[i * 2 + 1]);
        }
    }

    pair<vector<int>, vector<int>> fold(int l, int r) {
        pair<vector<int>, vector<int>> vl = identity, vr = identity;
        l += le; r += le;
        while (l < r) {
            if (l & 1) vl = func(vl, seg[l++]);
            if (r & 1) vr = func(seg[--r], vr);
            l /= 2; r /= 2;
        }
        return func(vl, vr);
    }
};

pair<unordered_map<int, int>, vector<int>> compress(const vector<int>& lst) {
    vector<int> sorted_lst = lst;
    sort(sorted_lst.begin(), sorted_lst.end());
    sorted_lst.erase(unique(sorted_lst.begin(), sorted_lst.end()), sorted_lst.end());

    unordered_map<int, int> comp;
    for (int i = 0; i < (int)sorted_lst.size(); ++i) {
        comp[sorted_lst[i]] = i;
    }
    return {comp, sorted_lst};
}

int main() {
    int N;
    cin >> N;
    vector<vector<int>> A(N);
    for (int i = 0; i < N; ++i) {
        int k;
        cin >> k;
        A[i].resize(k);
        for (int j = 0; j < k; ++j) {
            cin >> A[i][j];
        }
    }

    vector<int> all_values;
    for (const auto& vec : A) {
        all_values.insert(all_values.end(), vec.begin(), vec.end());
    }

    auto [comp, decomp] = compress(all_values);
    vector<int> L(N), R(N);
    for (int i = 0; i < N; ++i) {
        for (int& x : A[i]) {
            x = comp[x];
        }
        sort(A[i].begin(), A[i].end());
        L[i] = A[i].front();
        R[i] = A[i].back() + 1;
    }

    int le = comp.size();
    vector<vector<int>> query0(le + 1);
    vector<vector<pair<int,int>>> query1(le + 1);
    for (int i = 0; i < N; ++i) {
        query0[R[i]].push_back(L[i]);
        query1[L[i] + 1].emplace_back(R[i], i);
    }

    const int INF = INT_MAX;
    auto func = [](pair<vector<int>, vector<int>> a, pair<vector<int>, vector<int>> b) {
        vector<int> mi = a.first, ma = a.second;
        mi.insert(mi.end(), b.first.begin(), b.first.end());
        ma.insert(ma.end(), b.second.begin(), b.second.end());
        sort(mi.begin(), mi.end());
        sort(ma.rbegin(), ma.rend());
        mi.resize(min(2, (int)mi.size()));
        ma.resize(min(2, (int)ma.size()));
        return make_pair(mi, ma);
    };
    pair<vector<int>, vector<int>> identity = {{}, {}};
    SegmentTree st(le + 1, func, identity);

    vector<int> maxL(N, -INF), minR(N, INF);
    for (int r = le; r >= 0; --r) {
        for (int l : query0[r]) {
            st.set(l, func(st.fold(l, l + 1), {{r}, {l}}));
        }
        for (auto [b, i] : query1[r]) {
            auto [mi, ma] = st.fold(0, b);
            if (mi.size() > 1) {
                minR[i] = mi[0] == R[i] ? mi[1] : mi[0];
            }
            if (ma.size() > 1) {
                maxL[i] = ma[0] == L[i] ? ma[1] : ma[0];
            }
        }
    }

    vector<bool> one(N, false);
    for (int i = 0; i < N; ++i) {
        for (int x : A[i]) {
            if (maxL[i] < x && x < minR[i] - 1) {
                one[i] = true;
            }
        }
    }

    vector<int> idx(N);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int i, int j) {
        return R[i] < R[j];
    });

    int cur = 0, cnt = 0;
    for (int i : idx) {
        if (one[i] && cur <= L[i]) {
            cur = R[i];
            cnt++;
        }
    }

    int ans = cnt + (N - cnt) * 2;
    cout << ans << "\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3672kb

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: 3660kb

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: 3900kb

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: 3648kb

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3956kb

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:

177

result:

ok 1 number(s): "177"

Test #6:

score: 0
Accepted
time: 1ms
memory: 3796kb

input:

100
5 128474911 128789041 128389100 128571722 128449204
4 190783009 179144907 191954599 169739385
7 922968028 923017780 923012667 922993373 923012653 923010830 922983606
1 399117777
8 693609160 693615962 692956804 692902832 694104582 693605539 693750551 692909362
4 133590022 156691169 120354087 1477...

output:

175

result:

ok 1 number(s): "175"

Test #7:

score: 0
Accepted
time: 1ms
memory: 4024kb

input:

100
3 667874577 779650612 311873157
4 315088665 510831928 558038267 371108692
9 755153639 761562353 770756971 766146687 755341778 756786965 752029435 762376276 769269467
6 104846116 127832365 303763622 308914288 193368850 212600340
4 278400790 520739777 691975492 363532266
3 882063076 834874749 8790...

output:

188

result:

ok 1 number(s): "188"

Test #8:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

100
3 906356952 850278493 852337285
4 171262913 167082071 210705401 185031512
7 802495630 790288362 821278829 774987331 774050880 798490416 758938148
5 15709100 243583562 406822217 439043410 105298894
3 615900896 610909553 657678763
4 829696557 810959924 841612668 819869747
6 853997379 864469575 881...

output:

180

result:

ok 1 number(s): "180"

Test #9:

score: 0
Accepted
time: 1ms
memory: 3996kb

input:

100
4 364081200 540650381 353768306 122255830
7 936882622 937778158 941372288 943745873 947703805 938067346 944019473
7 598655091 679073706 723959930 579018281 860392698 852744534 665808681
1 557290205
3 838323287 764154463 864559801
4 952241609 888202173 792726290 886689636
6 653946054 841409940 83...

output:

175

result:

ok 1 number(s): "175"

Test #10:

score: 0
Accepted
time: 1ms
memory: 4028kb

input:

100
1 440195292
6 859787120 847131414 854112709 869067609 839981608 845676179
5 206450888 209708811 207370111 201853766 207539046
1 555976272
1 938758019
1 413646308
9 252799098 254947888 265345550 249752370 261338550 251583211 248642444 266900460 261558897
5 83936282 116530372 99708225 112074514 96...

output:

151

result:

ok 1 number(s): "151"

Test #11:

score: 0
Accepted
time: 1ms
memory: 3724kb

input:

100
1 146185204
6 852896086 841680008 855876871 835965157 843755423 851708745
1 629541324
6 85793267 91650449 93510560 99883657 85654258 98526112
3 495860961 497537876 493169484
5 454856746 450383319 452706190 450318327 452142745
6 183708510 180433221 182527046 181726412 181810362 181409052
4 692428...

output:

145

result:

ok 1 number(s): "145"

Test #12:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

100
5 689258498 593041024 495586014 514329370 820761943
7 205596594 194826463 204043065 193869609 214940002 212820377 193426959
7 765457074 564861616 742278670 649051551 719680647 625298040 628377100
7 964607721 975206807 980916305 899670280 950317349 907764973 966416652
14 583444762 587440679 37759...

output:

173

result:

ok 1 number(s): "173"

Test #13:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

100
4 333222379 411834962 321666960 375921743
6 469180085 599687470 434726418 542075515 468647205 585607083
3 329659185 334204906 442317787
7 407887487 331741182 273383133 416410227 418383971 588307977 271852141
4 865515303 869035169 860812055 861392741
5 641667472 860601686 753823004 793512791 9956...

output:

178

result:

ok 1 number(s): "178"

Test #14:

score: 0
Accepted
time: 1ms
memory: 4028kb

input:

100
7 690642381 613166525 688304596 634201428 562397003 633948538 679003753
4 47850900 39815477 89901918 122900559
1 531415583
6 138747627 198265925 498060210 473915860 275869244 10468108
6 855057160 887426020 927043300 863676485 864198874 851240046
5 692386595 513354859 610032533 595928682 63699127...

output:

175

result:

ok 1 number(s): "175"

Test #15:

score: -100
Time Limit Exceeded

input:

200000
1 158728811
3 820213140 695694229 890491786
2 223397517 576636349
3 886287626 840274568 787379583
2 531893033 375811452
4 208941903 362012920 456886582 677484638
2 658936887 741915526
1 163021123
3 102990858 99833598 128050246
2 880927685 395844417
2 582184019 506099921
2 503081931 890511277
...

output:

371392

result: