oj.uz

Submission #1047053

# Submission time Handle Problem Language Result Execution time Memory
1047053 2024-08-07T08:12:29 Z 변재우(#11026) Treatment Project (JOI20_treatment) C++17
100 / 100
 2337 ms 199800 KB 
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

const int Nmax=100010, S=(1<<17);
const ll INF=1e18;
int N, M;
ll ans=INF, D[Nmax];
struct Data {
    int t, l, r, c;
}A[Nmax];
vector<int> T, X1, X2;
priority_queue<pair<ll, int>> PQ;

struct Seg {
    set<pair<int, int>> Tree[2*S];
    void Update(int k, int x, int v) {Update(1, 1, S, k, x, v);}
    void Update(int node, int s, int e, int k, int x, int v) {
        Tree[node].insert({x, v});
        if(s==e) return;
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if(k<=m) Update(lch, s, m, k, x, v);
        else Update(rch, m+1, e, k, x, v);
    }
    int Query(int l, int r, int lo, int hi) {return Query(1, 1, S, l, r, lo, hi);}
    int Query(int node, int s, int e, int l, int r, int lo, int hi) {
        if(s>r || l>e) return -1;
        if(l<=s && e<=r) {
            auto p=Tree[node].lower_bound(make_pair(lo, 0));
            if(p!=Tree[node].end() && (*p).first<=hi) return (*p).second;
            else return -1;
        }
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        int tmp=Query(lch, s, m, l, r, lo, hi);
        if(tmp>0) return tmp;
        return Query(rch, m+1, e, l, r, lo, hi);
    }
    void Delete(int k, int x, int v) {Delete(1, 1, S, k, x, v);}
    void Delete(int node, int s, int e, int k, int x, int v) {
        Tree[node].erase({x, v});
        if(s==e) return;
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if(k<=m) Delete(lch, s, m, k, x, v);
        else Delete(rch, m+1, e, k, x, v);
    }
}P, P2;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    for(int i=1; i<=M; i++) {
        cin>>A[i].t>>A[i].l>>A[i].r>>A[i].c;
        A[i].r++;
        T.push_back(A[i].t);
        X1.push_back(A[i].l-A[i].t), X2.push_back(A[i].l+A[i].t);
    }
    sort(T.begin(), T.end()), T.erase(unique(T.begin(), T.end()), T.end());
    sort(X1.begin(), X1.end()), X1.erase(unique(X1.begin(), X1.end()), X1.end());
    sort(X2.begin(), X2.end()), X2.erase(unique(X2.begin(), X2.end()), X2.end());
    fill(D+1, D+M+1, INF);
    for(int i=1; i<=M; i++) {
        if(A[i].l==1) {
            D[i]=A[i].c, PQ.push({-D[i], i});
            continue;
        }
        P.Update(lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1, lower_bound(X1.begin(), X1.end(), A[i].l-A[i].t)-X1.begin()+1, i);
        P2.Update(lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1, lower_bound(X2.begin(), X2.end(), A[i].l+A[i].t)-X2.begin()+1, i);
    }
    while(!PQ.empty()) {
        int i=PQ.top().second; ll d=-PQ.top().first; PQ.pop();
        if(d!=D[i]) continue;
        while(true) {
            int t=P.Query(1, lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1, 1, upper_bound(X1.begin(), X1.end(), A[i].r-A[i].t)-X1.begin());
            if(t<0) break;
            if(D[t]>D[i]+A[t].c) D[t]=D[i]+A[t].c, PQ.push({-D[t], t});
            P.Delete(lower_bound(T.begin(), T.end(), A[t].t)-T.begin()+1, lower_bound(X1.begin(), X1.end(), A[t].l-A[t].t)-X1.begin()+1, t);
            P2.Delete(lower_bound(T.begin(), T.end(), A[t].t)-T.begin()+1, lower_bound(X2.begin(), X2.end(), A[t].l+A[t].t)-X2.begin()+1, t);
        }
        while(true) {
            int t=P2.Query(lower_bound(T.begin(), T.end(), A[i].t)-T.begin()+1, T.size(), 1, upper_bound(X2.begin(), X2.end(), A[i].r+A[i].t)-X2.begin());
            if(t<0) break;
            if(D[t]>D[i]+A[t].c) D[t]=D[i]+A[t].c, PQ.push({-D[t], t});
            P.Delete(lower_bound(T.begin(), T.end(), A[t].t)-T.begin()+1, lower_bound(X1.begin(), X1.end(), A[t].l-A[t].t)-X1.begin()+1, t);
            P2.Delete(lower_bound(T.begin(), T.end(), A[t].t)-T.begin()+1, lower_bound(X2.begin(), X2.end(), A[t].l+A[t].t)-X2.begin()+1, t);
        }
        if(A[i].r==N+1) ans=min(ans, D[i]);
    }
    if(ans==INF) cout<<-1;
    else cout<<ans;
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 197572 KB Output is correct
2 Correct 624 ms 197584 KB Output is correct
3 Correct 473 ms 156448 KB Output is correct
4 Correct 454 ms 156276 KB Output is correct
5 Correct 530 ms 197984 KB Output is correct
6 Correct 500 ms 197624 KB Output is correct
7 Correct 494 ms 197512 KB Output is correct
8 Correct 488 ms 196004 KB Output is correct
9 Correct 510 ms 197312 KB Output is correct
10 Correct 602 ms 197644 KB Output is correct
11 Correct 632 ms 199744 KB Output is correct
12 Correct 663 ms 199744 KB Output is correct
13 Correct 640 ms 199800 KB Output is correct
14 Correct 630 ms 199656 KB Output is correct
15 Correct 649 ms 197604 KB Output is correct
16 Correct 617 ms 197764 KB Output is correct
17 Correct 637 ms 197572 KB Output is correct
18 Correct 602 ms 199748 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 27224 KB Output is correct
2 Correct 3 ms 27316 KB Output is correct
3 Correct 3 ms 27228 KB Output is correct
4 Correct 3 ms 27328 KB Output is correct
5 Correct 4 ms 27228 KB Output is correct
6 Correct 3 ms 27228 KB Output is correct
7 Correct 3 ms 27228 KB Output is correct
8 Correct 3 ms 27228 KB Output is correct
9 Correct 3 ms 27072 KB Output is correct
10 Correct 3 ms 27332 KB Output is correct
11 Correct 4 ms 27228 KB Output is correct
12 Correct 3 ms 27228 KB Output is correct
13 Correct 3 ms 27228 KB Output is correct
14 Correct 4 ms 27224 KB Output is correct
15 Correct 3 ms 27228 KB Output is correct
16 Correct 3 ms 27276 KB Output is correct
17 Correct 3 ms 27228 KB Output is correct
18 Correct 3 ms 27248 KB Output is correct
19 Correct 3 ms 27228 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 27224 KB Output is correct
2 Correct 3 ms 27316 KB Output is correct
3 Correct 3 ms 27228 KB Output is correct
4 Correct 3 ms 27328 KB Output is correct
5 Correct 4 ms 27228 KB Output is correct
6 Correct 3 ms 27228 KB Output is correct
7 Correct 3 ms 27228 KB Output is correct
8 Correct 3 ms 27228 KB Output is correct
9 Correct 3 ms 27072 KB Output is correct
10 Correct 3 ms 27332 KB Output is correct
11 Correct 4 ms 27228 KB Output is correct
12 Correct 3 ms 27228 KB Output is correct
13 Correct 3 ms 27228 KB Output is correct
14 Correct 4 ms 27224 KB Output is correct
15 Correct 3 ms 27228 KB Output is correct
16 Correct 3 ms 27276 KB Output is correct
17 Correct 3 ms 27228 KB Output is correct
18 Correct 3 ms 27248 KB Output is correct
19 Correct 3 ms 27228 KB Output is correct
20 Correct 27 ms 33592 KB Output is correct
21 Correct 28 ms 33628 KB Output is correct
22 Correct 40 ms 35676 KB Output is correct
23 Correct 35 ms 35676 KB Output is correct
24 Correct 36 ms 34396 KB Output is correct
25 Correct 38 ms 35452 KB Output is correct
26 Correct 36 ms 35664 KB Output is correct
27 Correct 33 ms 35668 KB Output is correct
28 Correct 39 ms 34384 KB Output is correct
29 Correct 36 ms 35672 KB Output is correct
30 Correct 25 ms 35676 KB Output is correct
31 Correct 26 ms 35676 KB Output is correct
32 Correct 42 ms 35924 KB Output is correct
33 Correct 41 ms 35924 KB Output is correct
34 Correct 41 ms 35596 KB Output is correct
35 Correct 43 ms 35852 KB Output is correct
36 Correct 41 ms 35856 KB Output is correct
37 Correct 40 ms 35676 KB Output is correct

Subtask #4
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 197572 KB Output is correct
2 Correct 624 ms 197584 KB Output is correct
3 Correct 473 ms 156448 KB Output is correct
4 Correct 454 ms 156276 KB Output is correct
5 Correct 530 ms 197984 KB Output is correct
6 Correct 500 ms 197624 KB Output is correct
7 Correct 494 ms 197512 KB Output is correct
8 Correct 488 ms 196004 KB Output is correct
9 Correct 510 ms 197312 KB Output is correct
10 Correct 602 ms 197644 KB Output is correct
11 Correct 632 ms 199744 KB Output is correct
12 Correct 663 ms 199744 KB Output is correct
13 Correct 640 ms 199800 KB Output is correct
14 Correct 630 ms 199656 KB Output is correct
15 Correct 649 ms 197604 KB Output is correct
16 Correct 617 ms 197764 KB Output is correct
17 Correct 637 ms 197572 KB Output is correct
18 Correct 602 ms 199748 KB Output is correct
19 Correct 3 ms 27224 KB Output is correct
20 Correct 3 ms 27316 KB Output is correct
21 Correct 3 ms 27228 KB Output is correct
22 Correct 3 ms 27328 KB Output is correct
23 Correct 4 ms 27228 KB Output is correct
24 Correct 3 ms 27228 KB Output is correct
25 Correct 3 ms 27228 KB Output is correct
26 Correct 3 ms 27228 KB Output is correct
27 Correct 3 ms 27072 KB Output is correct
28 Correct 3 ms 27332 KB Output is correct
29 Correct 4 ms 27228 KB Output is correct
30 Correct 3 ms 27228 KB Output is correct
31 Correct 3 ms 27228 KB Output is correct
32 Correct 4 ms 27224 KB Output is correct
33 Correct 3 ms 27228 KB Output is correct
34 Correct 3 ms 27276 KB Output is correct
35 Correct 3 ms 27228 KB Output is correct
36 Correct 3 ms 27248 KB Output is correct
37 Correct 3 ms 27228 KB Output is correct
38 Correct 27 ms 33592 KB Output is correct
39 Correct 28 ms 33628 KB Output is correct
40 Correct 40 ms 35676 KB Output is correct
41 Correct 35 ms 35676 KB Output is correct
42 Correct 36 ms 34396 KB Output is correct
43 Correct 38 ms 35452 KB Output is correct
44 Correct 36 ms 35664 KB Output is correct
45 Correct 33 ms 35668 KB Output is correct
46 Correct 39 ms 34384 KB Output is correct
47 Correct 36 ms 35672 KB Output is correct
48 Correct 25 ms 35676 KB Output is correct
49 Correct 26 ms 35676 KB Output is correct
50 Correct 42 ms 35924 KB Output is correct
51 Correct 41 ms 35924 KB Output is correct
52 Correct 41 ms 35596 KB Output is correct
53 Correct 43 ms 35852 KB Output is correct
54 Correct 41 ms 35856 KB Output is correct
55 Correct 40 ms 35676 KB Output is correct
56 Correct 955 ms 156356 KB Output is correct
57 Correct 955 ms 155808 KB Output is correct
58 Correct 1177 ms 196812 KB Output is correct
59 Correct 1174 ms 196884 KB Output is correct
60 Correct 1314 ms 197468 KB Output is correct
61 Correct 1157 ms 196852 KB Output is correct
62 Correct 961 ms 156216 KB Output is correct
63 Correct 1022 ms 197480 KB Output is correct
64 Correct 1004 ms 197568 KB Output is correct
65 Correct 685 ms 197568 KB Output is correct
66 Correct 1302 ms 197572 KB Output is correct
67 Correct 1517 ms 196124 KB Output is correct
68 Correct 1270 ms 197316 KB Output is correct
69 Correct 1018 ms 197540 KB Output is correct
70 Correct 1753 ms 196516 KB Output is correct
71 Correct 1342 ms 197536 KB Output is correct
72 Correct 1031 ms 197516 KB Output is correct
73 Correct 1765 ms 196336 KB Output is correct
74 Correct 759 ms 197524 KB Output is correct
75 Correct 636 ms 197572 KB Output is correct
76 Correct 1824 ms 199632 KB Output is correct
77 Correct 1975 ms 199764 KB Output is correct
78 Correct 1924 ms 199780 KB Output is correct
79 Correct 2217 ms 197592 KB Output is correct
80 Correct 1972 ms 197672 KB Output is correct
81 Correct 1526 ms 197596 KB Output is correct
82 Correct 1967 ms 197524 KB Output is correct
83 Correct 2025 ms 197700 KB Output is correct
84 Correct 2337 ms 197332 KB Output is correct
85 Correct 1745 ms 197544 KB Output is correct
86 Correct 1797 ms 197576 KB Output is correct
87 Correct 1884 ms 197632 KB Output is correct
88 Correct 1539 ms 197572 KB Output is correct
89 Correct 1729 ms 197572 KB Output is correct
90 Correct 1830 ms 199644 KB Output is correct
91 Correct 1919 ms 198596 KB Output is correct
92 Correct 1864 ms 197576 KB Output is correct
93 Correct 2144 ms 197532 KB Output is correct
94 Correct 1897 ms 197644 KB Output is correct
95 Correct 1994 ms 197504 KB Output is correct
96 Correct 2007 ms 199684 KB Output is correct
97 Correct 1985 ms 199764 KB Output is correct
98 Correct 1936 ms 199740 KB Output is correct
99 Correct 1979 ms 199752 KB Output is correct
100 Correct 1617 ms 182972 KB Output is correct
101 Correct 1953 ms 199772 KB Output is correct
102 Correct 1841 ms 199736 KB Output is correct
103 Correct 1901 ms 197992 KB Output is correct