QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#807044 | #7849. Journey of Recovery | SGColin | AC ✓ | 382ms | 204672kb | C++20 | 2.9kb | 2024-12-09 18:30:42 | 2024-12-09 18:30:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tii;
typedef long long ll;
#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define N 1000007
inline int trans(int d, int h, int m) {return d * 1440 + h * 60 + m;}
inline tii recov(int t) {
int d = t / 1440; t %= 1440;
int h = t / 60; t %= 60;
return tie(d, h, t);
}
map<string, int> fid;
vector<int> S, seq;
int fidtot, u[N], v[N], s[N], t[N], id[N], rot[N], tot;
struct node {
int ls, rs, mn = 1e9;
} c[N << 4];
#define mid ((l + r) >> 1)
void upd(int &rt, int l, int r, int pos, int w) {
if (!rt) rt = ++tot;
if (l == r) {c[rt].mn = min(c[rt].mn, w); return;}
pos <= mid ? upd(c[rt].ls, l, mid, pos, w) : upd(c[rt].rs, mid + 1, r, pos, w);
c[rt].mn = min(c[c[rt].ls].mn, c[c[rt].rs].mn);
}
int query(int rt, int l, int r, int L, int R) {
if (!rt) return 1e9;
if (L <= l && r <= R) return c[rt].mn;
if (L > mid) return query(c[rt].rs, mid + 1, r, L, R);
if (R <= mid) return query(c[rt].ls, l, mid, L, R);
return min(query(c[rt].ls, l, mid, L, R), query(c[rt].rs, mid + 1, r, L, R));
}
bool sp[N];
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin >> n;
rep(i, 1, n) {
id[i] = i;
string nams, namt;
string tims, timt;
cin >> nams >> tims >> namt >> timt;
if (!fid[nams]) fid[nams] = ++fidtot; u[i] = fid[nams];
if (!fid[namt]) fid[namt] = ++fidtot; v[i] = fid[namt];
int tmp[3] = {0, 0, 0}, pos = 0;
for (auto x : tims) isdigit(x) ? tmp[pos] = tmp[pos] * 10 + (x ^ 48) : ++pos;
S.eb(s[i] = trans(tmp[0], tmp[1], tmp[2]));
tmp[0] = tmp[1] = tmp[2] = 0, pos = 0;
for (auto x : timt) isdigit(x) ? tmp[pos] = tmp[pos] * 10 + (x ^ 48) : ++pos;
S.eb(t[i] = trans(tmp[0], tmp[1], tmp[2]));
}
int m; cin >> m;
rep(i, 1, m) {int x; cin >> x; sp[x] = true; seq.eb(x);}
int TAR = v[seq.back()], TART = t[seq.back()];
S.eb(0); sort(all(S));
S.erase(unique(all(S)), S.end());
int ss = S.size();
auto getv = [&](int x) {return lower_bound(all(S), x) - S.begin() + 1;};
auto ask = [&](int u, int tim) {
if (u == TAR) return tim;
return query(rot[u], 1, ss, getv(tim), ss);
};
int ans = 0;
sort(id + 1, id + 1 + n, [&](int a, int b){return s[a] == s[b] ? sp[a] < sp[b] : s[a] > s[b];});
rep(i, 1, n) {
if (sp[id[i]]) {
int res = ask(u[id[i]], s[id[i]]);
if (res > 1e8) {puts("stranded"); return 0;}
ans = max(ans, res - TART);
}
int tt = ask(v[id[i]], t[id[i]]);
upd(rot[u[id[i]]], 1, ss, getv(s[id[i]]), tt);
}
printf("%d\n", ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 8ms
memory: 191372kb
input:
8 egnx 0d00:10 delft 0d01:00 delft 0d01:00 zad 0d09:00 zad 0d09:01 prg 0d15:30 prg 0d20:00 delft 1d02:15 prg 0d22:00 delft 1d04:15 zad 2d00:00 delft 3d00:00 egnx 2d00:00 delft 2d02:00 egnx 2d00:00 delft 2d02:00 4 1 2 3 4
output:
2745
result:
ok single line: '2745'
Test #2:
score: 0
Accepted
time: 7ms
memory: 191380kb
input:
3 ork 101d00:00 noc 101d00:01 ork 100d23:59 noc 101d00:02 dub 100d00:00 ork 101d00:00 2 3 1
output:
stranded
result:
ok single line: 'stranded'
Test #3:
score: 0
Accepted
time: 12ms
memory: 191664kb
input:
2 lax 0d00:30 hnl 0d06:20 lax 0d00:30 hnl 0d06:20 1 2
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 19ms
memory: 191404kb
input:
20 baa 0d00:31 bab 0d00:32 baa 0d00:15 bab 0d00:53 baa 0d00:44 bab 0d00:47 baa 0d00:11 bab 0d00:42 baa 0d00:15 bab 0d00:27 baa 0d00:19 bab 0d00:20 baa 0d00:16 bab 0d00:40 baa 0d00:07 bab 0d00:54 baa 0d00:25 bab 0d00:44 baa 0d00:32 bab 0d00:42 bab 0d00:56 bac 0d01:17 bab 0d01:10 bac 0d01:20 bab 0d01:...
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 192116kb
input:
90 baa 0d00:06 bab 0d00:37 baa 0d00:49 bab 0d00:52 baa 0d00:05 bab 0d00:27 baa 0d00:26 bab 0d00:27 baa 0d00:03 bab 0d00:36 baa 0d00:23 bab 0d00:31 baa 0d00:01 bab 0d00:55 baa 0d00:39 bab 0d00:42 baa 0d00:28 bab 0d00:44 baa 0d00:04 bab 0d00:38 bab 0d01:20 bac 0d01:35 bab 0d01:45 bac 0d01:52 bab 0d01:...
output:
21
result:
ok single line: '21'
Test #6:
score: 0
Accepted
time: 12ms
memory: 191304kb
input:
7 bac 3d00:06 bab 39d22:17 bab 74d04:02 baa 81d19:39 baa 12d18:01 bab 86d01:31 baa 48d07:23 bac 67d05:42 bac 34d21:56 bab 50d08:26 bac 0d05:31 baa 1d05:40 bac 0d01:38 baa 0d15:10 1 7
output:
870
result:
ok single line: '870'
Test #7:
score: 0
Accepted
time: 8ms
memory: 191316kb
input:
17 bac 74d16:04 bae 98d19:52 bad 8d22:44 bab 12d05:58 bac 13d19:03 bae 77d05:09 baa 65d12:55 bad 98d21:21 baa 44d00:55 bae 85d14:23 bab 16d16:49 baa 82d09:17 bac 22d11:24 baa 56d11:42 bad 52d19:22 bab 95d14:48 bac 87d05:01 bae 99d06:27 bad 11d00:59 bae 40d23:57 bad 49d23:49 bac 51d04:56 bab 87d16:37...
output:
121500
result:
ok single line: '121500'
Test #8:
score: 0
Accepted
time: 4ms
memory: 191244kb
input:
1292 bda 27d03:01 bbh 84d17:32 bdd 29d08:34 bdg 79d12:41 beb 58d02:11 bdh 83d03:09 bcd 25d22:40 bdj 54d04:08 bbf 61d05:55 bbi 66d03:11 bbf 55d17:45 bcj 69d08:21 bcf 77d08:04 bea 97d14:00 bah 67d00:16 bbc 68d00:51 bdj 33d00:22 bcd 78d09:32 bej 33d00:36 beb 74d23:07 bee 44d05:33 bdc 54d14:34 bbc 11d04...
output:
stranded
result:
ok single line: 'stranded'
Test #9:
score: 0
Accepted
time: 16ms
memory: 191792kb
input:
5084 bfi 30d16:18 bhb 53d00:34 bhb 13d00:48 bee 35d05:13 bdf 31d15:19 bda 51d18:11 bgi 85d12:26 bjj 87d17:41 bdi 81d19:03 bdf 97d21:24 bbj 35d13:39 bda 57d08:21 bbf 9d01:40 baj 91d13:52 bhc 30d03:05 bfd 96d00:19 bbh 82d22:44 bbd 91d21:34 bhe 18d20:16 bje 85d17:38 bad 45d03:58 bag 98d00:20 bba 33d04:...
output:
71921
result:
ok single line: '71921'
Test #10:
score: 0
Accepted
time: 382ms
memory: 204672kb
input:
500834 gfg 51d23:48 jhh 90d07:46 iee 39d21:18 cga 71d19:14 dha 86d16:25 hih 97d06:29 gef 20d02:03 djj 90d15:23 bgb 12d20:08 bjc 15d23:38 cgc 17d02:37 ede 94d06:39 cjj 47d10:47 fbb 93d23:36 cjf 61d20:43 hba 74d15:30 ibe 27d14:46 ice 57d22:24 cgj 57d08:11 hdc 63d17:09 hcj 28d08:25 ghe 51d14:40 hcf 33d...
output:
stranded
result:
ok single line: 'stranded'
Test #11:
score: 0
Accepted
time: 20ms
memory: 192212kb
input:
9990 baa 0d00:49 bab 0d00:51 baa 0d00:35 bab 0d00:36 baa 0d00:20 bab 0d00:34 baa 0d00:01 bab 0d00:03 baa 0d00:35 bab 0d00:41 baa 0d00:30 bab 0d00:43 baa 0d00:09 bab 0d00:59 baa 0d00:12 bab 0d00:42 baa 0d00:10 bab 0d00:27 baa 0d00:43 bab 0d00:44 bab 0d00:26 bac 0d00:46 bab 0d00:41 bac 0d00:58 bab 0d0...
output:
stranded
result:
ok single line: 'stranded'
Test #12:
score: 0
Accepted
time: 83ms
memory: 194400kb
input:
99990 baa 0d00:07 bab 0d00:23 baa 0d00:45 bab 0d00:47 baa 0d00:07 bab 0d00:42 baa 0d00:04 bab 0d00:32 baa 0d00:15 bab 0d00:46 baa 0d00:14 bab 0d00:40 baa 0d00:10 bab 0d00:29 baa 0d00:01 bab 0d00:45 baa 0d00:18 bab 0d00:22 baa 0d00:06 bab 0d00:45 bab 0d00:45 bac 0d01:01 bab 0d00:59 bac 0d01:05 bab 0d...
output:
stranded
result:
ok single line: 'stranded'