QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#798235 | #9786. Magical Bags | vwxyz | TL | 1ms | 4028kb | C++23 | 4.1kb | 2024-12-04 09:56:39 | 2024-12-04 09:56:40 |
Judging History
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