QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #855365 | #9730. Elevator II | SorahISA | AC ✓ | 75ms | 8468kb | C++23 | 11.2kb | 2025-01-12 19:12:34 | 2025-01-12 19:12:40 |
Judging History
answer
#ifndef SorahISA
#define SorahISA
#include SorahISA __FILE__ SorahISA
void solve() {
int N, F; cin >> N >> F;
vector<array<int, 3>> itv(N);
for (int tok = 0; auto &[l, r, id] : itv) cin >> l >> r, id = ++tok;
sort(ALL(itv));
int ans = 0;
vector<int> seq, used(N+1, 0);
for (int cur = F; auto [l, r, id] : itv) {
ans += r - l;
if (l > cur) ans += l - cur;
if (chmax(cur, r)) seq.eb(id), used[id] = 1;
}
for (auto [l, r, id] : itv | views::reverse) {
if (not used[id]) seq.eb(id), used[id] = 1;
}
print(ans);
print(seq);
}
int32_t main() {
fastIO();
int t = 1; cin >> t;
for (int _ = 1; _ <= t; ++_) {
// cout << "Case #" << _ << ": ";
solve();
}
return 0;
}
#else
#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #include <bits/extc++.h>
// #include <tr2/dynamic_bitset>
using i64 = long long;
using i128 = __int128;
#define int i64
using f80 = long double;
using f128 = __float128;
#define double f80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;
// #define X first
// #define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())
#define popcnt(x) __builtin_popcountll(x)
// template <size_t D, typename T> struct Vec : vector<Vec<D-1, T>> {
// static_assert(D >= 1, "Vector dimension must be greater than zero!");
// template <typename... Args> Vec(int n = 0, Args... args) : vector<Vec<D-1, T>>(n, Vec<D-1, T>(args...)) {}
// };
// template <typename T> struct Vec<1, T> : vector<T> {
// Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {}
// };
template <typename T> ostream& operator << (ostream &os, const vector<T> &vec)
{ for (size_t i = 0; i < size(vec); ++i) { if (i) os << " "; os << vec[i]; } return os; }
#ifdef local
#define fastIO() void()
#define debug(...) \
_color.emplace_back("\u001b[31m"), \
fprintf(stderr, "%sAt [%s], line %d: (%s) = ", _color.back().c_str(), __FUNCTION__, __LINE__, #__VA_ARGS__), \
_do(__VA_ARGS__), _color.pop_back(), \
fprintf(stderr, "%s", _color.back().c_str())
#define print(...) \
fprintf(stdout, "%s", "\u001b[36m"), \
_P(__VA_ARGS__), \
fprintf(stdout, "%s", "\u001b[0m")
deque<string> _color{"\u001b[0m"};
template <typename T> concept is_string = is_same_v<T, string&> or is_same_v<T, const string&>;
template <typename T> concept is_iterable = requires (T _t) { begin(_t); };
template <typename T> inline void _print_err(T &&_t);
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(const tuple<U...> &_t);
template <size_t I, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &);
template <size_t I, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(tuple<U...> &_t);
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu);
inline void _do() { cerr << "\n"; }
template <typename T> inline void _do(T &&_t) { _print_err(_t), cerr << "\n"; }
template <typename T, typename ...U> inline void _do(T &&_t, U &&..._u) { _print_err(_t), cerr << ", ", _do(_u...); }
#else
#define fastIO() cin.tie(0)->sync_with_stdio(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#endif
inline void _P() { cout << "\n"; }
template <typename T> inline void _P(T &&_t) { cout << _t << "\n"; }
template <typename T, typename ...U> inline void _P(T &&_t, U &&..._u) { cout << _t << " ", _P(_u...); }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int getRand(int L, int R) {
if (L > R) swap(L, R);
return (int)(rng() % ((uint64_t)R - L + 1) + L);
}
template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
template <typename T, typename U> bool chmax(T &lhs, U rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; }
template <typename T> void make_unique(vector<T> &vec) {
if (not is_sorted(ALL(vec))) sort(ALL(vec));
vec.erase(unique(ALL(vec)), end(vec));
}
/// below are Fast I/O and _print_err templates ///
/*
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
#include <unistd.h>
const int S = 65536;
int OP = 0;
char OB[S];
inline char RC() {
static char buf[S], *p = buf, *q = buf;
return p == q and (q = (p = buf) + read(0, buf, S)) == buf ? -1 : *p++;
}
inline int RI() {
static char c;
int a;
while (((c = RC()) < '0' or c > '9') and c != '-' and c != -1);
if (c == '-') {
a = 0;
while ((c = RC()) >= '0' and c <= '9') a *= 10, a -= c ^ '0';
}
else {
a = c ^ '0';
while ((c = RC()) >= '0' and c <= '9') a *= 10, a += c ^ '0';
}
return a;
}
inline void WI(int n, char c = '\n') {
static char buf[20], p;
if (n == 0) OB[OP++] = '0';
p = 0;
if (n < 0) {
OB[OP++] = '-';
while (n) buf[p++] = '0' - (n % 10), n /= 10;
}
else {
while (n) buf[p++] = '0' + (n % 10), n /= 10;
}
for (--p; p >= 0; --p) OB[OP++] = buf[p];
OB[OP++] = c;
if (OP > S-20) write(1, OB, OP), OP = 0;
}
/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
*/
#ifdef local
template <typename T> inline void _print_err(T &&_t) { cerr << _t; }
template <typename T> inline void _print_err(T &&_t) requires is_iterable<T> and (not is_string<T>) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back() << "[";
for (bool _first = true; auto &_x : _t) {
if (!_first) cerr << ", ";
_print_err(_x), _first = false;
}
cerr << "]" << (_color.pop_back(), _color.back());
}
template <typename T, typename U> ostream& operator << (ostream &os, const pair<T, U> &_tu) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back() << "(";
_print_err(_tu.first), cerr << ", ", _print_err(_tu.second);
cerr << ")" << (_color.pop_back(), _color.back());
return os;
}
template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(const tuple<U...> &) {
cerr << ")" << (_color.pop_back(), _color.back());
}
template <size_t I = 0, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(const tuple<U...> &_t) {
if (!I) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back();
}
cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}
template <size_t I = 0, typename ...U> inline typename enable_if<I == sizeof...(U), void>::type _print_err(tuple<U...> &) {
cerr << ")" << (_color.pop_back(), _color.back());
}
template <size_t I = 0, typename ...U> inline typename enable_if<I < sizeof...(U), void>::type _print_err(tuple<U...> &_t) {
if (!I) {
_color.emplace_back(_color.back()), ++_color.back()[3];
cerr << _color.back();
}
cerr << (I ? ", " : "("), _print_err(get<I>(_t)), _print_err<I+1, U...>(_t);
}
#endif
#endif
/**
*
*
*
* iiiiii iiiiiiiiii iiiiiiiiiiiiii
* iiiiiiiiiiiii iiiiiii iiii iiiiiiiiiiiiiii ii iiii
* iiiiiiii iiiiiiiii iiii iiii iii iii iiiiiiiiii
* iiiiiii iiiiii iiii iiii ii iiiiiiiiii iiii iiii
* iiiiii iiiii iiii iiii iii iiii iiiiiiiiiiiiiiiii ii
* iiiiii iiiiiii iiiiiii iiiiiiii iii iiiiiiiiiiiiii iii iiii
* iiiiii iiiiiii iiiii ii iiii iiiiiiiiiii iiii iii iiii iiii iii
* iiiii iiiiiiii ii iiiii iiii iiiiiiiii iii iii iii iii ii iiii
* iiiiii iiiiiiii iiiii iiiii iiiiiiiiiiiiiiii iii iii ii iii iii iiii
* iiiii iiiiii iiii iiiiii iiiiiii iii iii iiii ii i ii iii iii
* iiiiii iiii iiiiiiiiiiiiiii iii iiii iiiii iii ii iii iii ii
* iiiii iiiiiiii iiiiiiiiii iiii iiiiiiiii ii iii ii
* iiiii iiiiii iiii iiiii iii ii ii i
* iiiiii iiiiiiii iiiii iiiii ii ii ii
* iiiii iiii iiii iiiiiiiiiiii ii
* iii iiii iiii iiiiiiii
* iiiii iiii
* iiii iiii
* iiii iiiii
* iii iiiii
* iii iiiii
* iii iiiiii
* iiiiiiiii
* iiiiii
*
*
*
**/
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3704kb
input:
2 4 2 3 6 1 3 2 7 5 6 2 5 2 4 6 8
output:
11 2 3 4 1 5 2 1
result:
ok ok 2 cases (2 test cases)
Test #2:
score: 0
Accepted
time: 44ms
memory: 3692kb
input:
6100 19 52 51 98 2 83 40 58 96 99 39 55 72 94 15 17 4 15 48 99 2 99 77 78 35 77 44 62 79 81 30 31 1 48 48 76 68 99 60 66 6 19 44 53 64 92 17 28 67 98 9 99 40 65 16 27 99 100 15 56 4 6 24 97 84 96 47 49 37 38 77 79 13 40 13 92 71 100 47 93 90 91 72 81 15 48 32 71 19 17 95 99 10 23 18 100 90 93 52 92 ...
output:
524 2 10 4 14 11 6 18 19 1 9 17 13 3 5 12 15 7 8 16 194 5 4 2 1 6 3 397 9 10 4 11 1 13 5 8 14 12 6 7 16 2 15 3 733 2 9 15 7 11 3 1 4 17 8 16 5 12 10 19 13 14 6 18 244 3 10 14 5 6 2 8 12 4 11 1 15 9 13 7 422 17 18 11 10 6 7 2 13 4 20 8 5 9 15 16 14 1 19 3 12 104 3 4 1 2 187 4 3 8 2 1 5 6 9 10 7 117 2...
result:
ok ok 6100 cases (6100 test cases)
Test #3:
score: 0
Accepted
time: 71ms
memory: 8344kb
input:
3 100000 9859 150464 951410 637107 897197 236268 936879 353406 403927 511229 999416 861211 958428 186246 446149 162388 805753 449016 817386 147119 604340 579101 926848 958992 987299 859662 907007 507058 690951 719158 856587 789149 927957 691705 707085 694110 845505 192759 616586 905489 935507 937041...
output:
24903933702 93759 83950 38185 82687 92856 81216 75880 21862 39096 65801 72396 12929 65474 13509 51617 64518 1391 17116 69859 94976 86643 52272 9868 78418 75539 36677 50759 70692 43527 59278 99948 47680 41692 64055 27729 7685 22139 91293 15697 79107 7904 25422 23408 55091 95233 84324 21636 79982 8954...
result:
ok ok 3 cases (3 test cases)
Test #4:
score: 0
Accepted
time: 62ms
memory: 8468kb
input:
3 100000 932101 80818 80823 538842 538844 406812 406818 625053 625054 511066 511073 667363 667365 527022 527023 621329 621331 855832 855852 796168 796169 268927 268929 650891 650895 312793 312794 873256 873260 424896 424929 266271 266272 902201 902209 842863 842864 361599 361610 647851 647855 148132...
output:
986597 61385 82641 30352 11990 41160 74602 95031 34312 64927 10872 13641 70364 69688 42804 83583 94175 77157 82305 60601 21546 50908 21059 98950 61273 47916 86818 9311 25865 48329 56510 29951 79449 26301 33491 4366 96045 59186 89170 37084 66953 58554 99074 38280 78061 69175 74069 26606 30169 81023 7...
result:
ok ok 3 cases (3 test cases)
Test #5:
score: 0
Accepted
time: 75ms
memory: 8352kb
input:
3 100000 375117879 637628712 637644704 788784579 788792294 804734775 804734822 332639566 332642798 143113598 143114045 132119073 132122341 684483097 684513821 484676670 484678332 661667340 661668818 777865379 777870254 142495696 142495995 101735856 101740588 906481102 906481965 360087766 360091064 1...
output:
872643717 43549 34676 31878 49124 12077 8140 13605 76831 10834 96613 83688 46028 65944 14511 56152 84791 1759 60404 73244 38124 93732 74294 8688 64153 56500 39213 27938 93350 21680 36926 8295 8832 69685 1025 22233 14796 83881 83105 72820 95432 90168 29163 20496 4937 51441 96515 46657 82775 90528 380...
result:
ok ok 3 cases (3 test cases)
Extra Test:
score: 0
Extra Test Passed