QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#807044#7849. Journey of RecoverySGColinAC ✓382ms204672kbC++202.9kb2024-12-09 18:30:422024-12-09 18:30:42

Judging History

This is the latest submission verdict.

  • [2024-12-09 18:30:42]
  • Judged
  • Verdict: AC
  • Time: 382ms
  • Memory: 204672kb
  • [2024-12-09 18:30:42]
  • Submitted

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'