QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#814470 | #9786. Magical Bags | ucup-team4967# | WA | 1ms | 3796kb | C++23 | 2.2kb | 2024-12-14 17:46:48 | 2024-12-14 17:47:07 |
Judging History
answer
#include <bits/extc++.h>
using ll = long long;
using pll = std::pair<ll, ll>;
using pii = std::pair<int, int>;
template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& xs) {
for (T& x : xs) is >> x;
return is;
}
template <class T>
bool chmax(T& x, const T& v) {
if (x < v) {
x = v;
return true;
} else {
return false;
}
}
template <class T>
bool chmin(T& x, const T& v) {
if (x > v) {
x = v;
return true;
} else {
return false;
}
}
int main() {
int N;
std::cin >> N;
int ans = 0;
std::vector<std::deque<ll>> bags(N);
for (int i = 0; i < N; i++) {
int K;
std::cin >> K;
ans += K;
std::vector<ll> ttt;
for (int k = 0; k < K; k++) {
ll tmp;
std::cin >> tmp;
ttt.push_back(tmp);
}
std::ranges::sort(ttt);
for (ll x : ttt) {
bags[i].push_back(x);
}
}
using event = std::tuple<int, int, int>;
auto ooooo = [&](bool rev = false) {
std::vector<event> events;
for (int i = 0; i < N; i++) {
events.emplace_back(bags[i].back(), 1, i);
}
std::ranges::sort(events);
// if (rev) {
// std::ranges::reverse(events);
// }
std::vector<ll> pops;
for (auto [x, f, i] : events) {
// x = std::abs(x);
if (f == 1) {
auto it = std::ranges::lower_bound(pops, bags[i].front());
// std::cerr << "bag " << i << ": ";
if (it == pops.end()) {
bags[i].clear();
bags[i].push_back(x);
// std::cerr << "pop all" << std::endl;
} else {
while (bags[i].size() > 1 && bags[i][1] < *it) {
bags[i].pop_front();
// std::cerr << "pop ";
}
// std::cerr << std::endl;
}
pops.push_back(x);
}
}
};
ooooo();
for (auto& bag : bags) {
std::vector<ll> tmp(bag.begin(), bag.end());
std::ranges::reverse(tmp);
bag.clear();
for (ll x : tmp) {
bag.push_back(-x);
}
}
ooooo(true);
ans = 0;
for (int i = 0; i < N; i++) {
ans += std::min(bags[i].size(), 2UL);
}
std::cout << ans << std::endl;
// for (int i = 0; i < N; i++) {
// for (ll x : bags[i]) {
// std::cerr << x << " ";
// }
//
// std::cerr << "\n";
// }
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3536kb
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: 3600kb
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: 3536kb
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: 3796kb
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: 3660kb
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: -100
Wrong Answer
time: 1ms
memory: 3612kb
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:
176
result:
wrong answer 1st numbers differ - expected: '175', found: '176'