oj.uz

Submission #538179

# Submission time Handle Problem Language Result Execution time Memory
538179 2022-03-16T07:33:15 Z wiwiho Treatment Project (JOI20_treatment) C++14
100 / 100
 698 ms 103348 KB 
#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 1LL << 60;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

struct treat{
    ll t, l, r, c;
};

int n, K, m;
vector<ll> dis;
vector<treat> a;
std::priority_queue<pll, vector<pll>, greater<>> pq;

#define lc (2 * id + 1)
#define rc (2 * id + 2)

struct SegmentTree{
    vector<vector<pll>> st;

    void init(){
        st.resize(4 * m);
    }

    void add(int x, pll v, int L = 0, int R = m - 1, int id = 0){
        //cerr << "add " << v << " " << id << "\n";
        st[id].eb(v);
        if(L == R){
            return;
        }
        int M = (L + R) / 2;
        if(x <= M) add(x, v, L, M, lc);
        else add(x, v, M + 1, R, rc);
    }

    void relax(int l, int r, int mx, ll d, int L = 0, int R = m - 1, int id = 0){
        if(l <= L && R <= r){
            //cerr << "sgt relax " << l << " " << r << " " << L << " " << R << " " << id << "\n";
            //printv(st[id], cerr);
            while(!st[id].empty() && st[id].back().F <= mx){
                int now = st[id].back().S;
                if(dis[now] <= d + a[now].c){
                    st[id].pob;
                    continue;
                }
                //cerr << "ok " << now << "\n";
                dis[now] = d + a[now].c;
                pq.push(mp(dis[now], now));
                st[id].pob;
            }
            return;
        }
        int M = (L + R) / 2;
        if(r <= M) relax(l, r, mx, d, L, M, lc);
        else if(l > M) relax(l, r, mx, d, M + 1, R, rc);
        else{
            relax(l, r, mx, d, L, M, lc);
            relax(l, r, mx, d, M + 1, R, rc);
        }
    }

};

int main(){
    StarBurstStream

    cin >> n >> K;
    a.resize(K + 1);
    dis.resize(K + 1, MAX);

    vector<int> tmp;

    SegmentTree st1, st2;

    for(int i = 1; i <= K; i++){
        cin >> a[i].t >> a[i].l >> a[i].r >> a[i].c;
        tmp.eb(a[i].t);
    }
    lsort(tmp);
    uni(tmp);
    m = tmp.size();
    st1.init(); st2.init();

    for(int i = 1; i <= K; i++){
        int x = lower_bound(iter(tmp), a[i].t) - tmp.begin();
        st1.add(x, mp(-(a[i].t - a[i].l), i));
        st2.add(x, mp(a[i].t + a[i].l, i));
    }

    for(int i = 0; i < 4 * m; i++){
        gsort(st1.st[i]);
        gsort(st2.st[i]);
    }

    for(int i = 1; i <= K; i++){
        if(a[i].l == 1){
            dis[i] = a[i].c;
            pq.push(mp(a[i].c, i));
        }
    }
    
    while(!pq.empty()){
        int now = pq.top().S;
        ll d = pq.top().F;
        pq.pop();
        if(d != dis[now]) continue;
        int x = lower_bound(iter(tmp), a[now].t) - tmp.begin();
        //cerr << "relax1 " << now << "\n";
        st1.relax(0, x, -(a[now].t - a[now].r - 1), d);
        //cerr << "relax2 " << now << "\n";
        st2.relax(x, m - 1, a[now].r + a[now].t + 1, d);
    }

    ll ans = MAX;
    for(int i = 1; i <= K; i++){
        if(a[i].r == n){
            ans = min(ans, dis[i]);
        }
    }
    if(ans == MAX) ans = -1;
    cout << ans << "\n";

    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 9544 KB Output is correct
2 Correct 68 ms 10004 KB Output is correct
3 Correct 72 ms 10868 KB Output is correct
4 Correct 72 ms 10056 KB Output is correct
5 Correct 76 ms 12192 KB Output is correct
6 Correct 69 ms 10032 KB Output is correct
7 Correct 65 ms 10020 KB Output is correct
8 Correct 57 ms 9952 KB Output is correct
9 Correct 55 ms 10032 KB Output is correct
10 Correct 55 ms 9964 KB Output is correct
11 Correct 78 ms 12220 KB Output is correct
12 Correct 80 ms 12184 KB Output is correct
13 Correct 74 ms 12248 KB Output is correct
14 Correct 80 ms 12156 KB Output is correct
15 Correct 67 ms 10008 KB Output is correct
16 Correct 66 ms 9972 KB Output is correct
17 Correct 67 ms 10020 KB Output is correct
18 Correct 76 ms 12156 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 14 ms 4108 KB Output is correct
21 Correct 19 ms 4076 KB Output is correct
22 Correct 12 ms 3204 KB Output is correct
23 Correct 12 ms 3156 KB Output is correct
24 Correct 19 ms 4956 KB Output is correct
25 Correct 14 ms 4944 KB Output is correct
26 Correct 14 ms 4844 KB Output is correct
27 Correct 12 ms 4816 KB Output is correct
28 Correct 15 ms 5076 KB Output is correct
29 Correct 14 ms 4980 KB Output is correct
30 Correct 13 ms 4948 KB Output is correct
31 Correct 12 ms 4808 KB Output is correct
32 Correct 16 ms 5164 KB Output is correct
33 Correct 19 ms 5172 KB Output is correct
34 Correct 15 ms 4304 KB Output is correct
35 Correct 17 ms 5072 KB Output is correct
36 Correct 17 ms 5052 KB Output is correct
37 Correct 15 ms 4280 KB Output is correct

Subtask #4
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 9544 KB Output is correct
2 Correct 68 ms 10004 KB Output is correct
3 Correct 72 ms 10868 KB Output is correct
4 Correct 72 ms 10056 KB Output is correct
5 Correct 76 ms 12192 KB Output is correct
6 Correct 69 ms 10032 KB Output is correct
7 Correct 65 ms 10020 KB Output is correct
8 Correct 57 ms 9952 KB Output is correct
9 Correct 55 ms 10032 KB Output is correct
10 Correct 55 ms 9964 KB Output is correct
11 Correct 78 ms 12220 KB Output is correct
12 Correct 80 ms 12184 KB Output is correct
13 Correct 74 ms 12248 KB Output is correct
14 Correct 80 ms 12156 KB Output is correct
15 Correct 67 ms 10008 KB Output is correct
16 Correct 66 ms 9972 KB Output is correct
17 Correct 67 ms 10020 KB Output is correct
18 Correct 76 ms 12156 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 316 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 320 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 212 KB Output is correct
38 Correct 14 ms 4108 KB Output is correct
39 Correct 19 ms 4076 KB Output is correct
40 Correct 12 ms 3204 KB Output is correct
41 Correct 12 ms 3156 KB Output is correct
42 Correct 19 ms 4956 KB Output is correct
43 Correct 14 ms 4944 KB Output is correct
44 Correct 14 ms 4844 KB Output is correct
45 Correct 12 ms 4816 KB Output is correct
46 Correct 15 ms 5076 KB Output is correct
47 Correct 14 ms 4980 KB Output is correct
48 Correct 13 ms 4948 KB Output is correct
49 Correct 12 ms 4808 KB Output is correct
50 Correct 16 ms 5164 KB Output is correct
51 Correct 19 ms 5172 KB Output is correct
52 Correct 15 ms 4304 KB Output is correct
53 Correct 17 ms 5072 KB Output is correct
54 Correct 17 ms 5052 KB Output is correct
55 Correct 15 ms 4280 KB Output is correct
56 Correct 550 ms 82228 KB Output is correct
57 Correct 541 ms 82804 KB Output is correct
58 Correct 501 ms 80840 KB Output is correct
59 Correct 516 ms 80956 KB Output is correct
60 Correct 374 ms 64120 KB Output is correct
61 Correct 503 ms 80760 KB Output is correct
62 Correct 535 ms 82328 KB Output is correct
63 Correct 561 ms 96324 KB Output is correct
64 Correct 588 ms 96612 KB Output is correct
65 Correct 82 ms 12056 KB Output is correct
66 Correct 344 ms 63940 KB Output is correct
67 Correct 502 ms 95848 KB Output is correct
68 Correct 426 ms 95536 KB Output is correct
69 Correct 378 ms 92848 KB Output is correct
70 Correct 585 ms 95836 KB Output is correct
71 Correct 448 ms 95276 KB Output is correct
72 Correct 395 ms 95136 KB Output is correct
73 Correct 586 ms 95860 KB Output is correct
74 Correct 314 ms 95348 KB Output is correct
75 Correct 272 ms 95188 KB Output is correct
76 Correct 580 ms 88248 KB Output is correct
77 Correct 646 ms 99400 KB Output is correct
78 Correct 640 ms 88048 KB Output is correct
79 Correct 692 ms 100080 KB Output is correct
80 Correct 640 ms 88484 KB Output is correct
81 Correct 504 ms 100060 KB Output is correct
82 Correct 657 ms 87992 KB Output is correct
83 Correct 698 ms 99116 KB Output is correct
84 Correct 676 ms 99304 KB Output is correct
85 Correct 632 ms 100044 KB Output is correct
86 Correct 623 ms 100336 KB Output is correct
87 Correct 618 ms 100012 KB Output is correct
88 Correct 611 ms 100076 KB Output is correct
89 Correct 603 ms 100132 KB Output is correct
90 Correct 668 ms 103348 KB Output is correct
91 Correct 661 ms 101972 KB Output is correct
92 Correct 627 ms 99984 KB Output is correct
93 Correct 655 ms 100224 KB Output is correct
94 Correct 685 ms 100064 KB Output is correct
95 Correct 670 ms 100052 KB Output is correct
96 Correct 649 ms 103136 KB Output is correct
97 Correct 668 ms 103088 KB Output is correct
98 Correct 650 ms 103052 KB Output is correct
99 Correct 638 ms 103008 KB Output is correct
100 Correct 679 ms 103056 KB Output is correct
101 Correct 661 ms 103008 KB Output is correct
102 Correct 637 ms 103168 KB Output is correct
103 Correct 591 ms 100276 KB Output is correct