oj.uz

Submission #408678

# Submission time Handle Problem Language Result Execution time Memory
408678 2021-05-19T13:08:17 Z doowey Treatment Project (JOI20_treatment) C++14
100 / 100
 2518 ms 273464 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 10;
const ll inf = (ll)1e18;
ll T[N];
ll L[N];
ll R[N];
ll C[N];

ll dist[N];
bool pro[N];

vector<int> lis;

struct segm{
    set<pii> kick[N*4+512];
    void ins(int node, int cl, int cr, int id, ll fa, int fb){
        kick[node].insert(mp(fa,fb));
        if(cl == cr) return;
        int mid = (cl + cr) / 2;
        if(mid >= id)
            ins(node * 2, cl, mid, id, fa, fb);
        else
            ins(node * 2 + 1, mid + 1, cr, id, fa, fb);
    }
    void get(int node, int cl, int cr, int tl, int tr, ll val, int mode){
        if(cr < tl || cl > tr) return;
        if(cl >= tl && cr <= tr){
            if(mode == 0){ // get <= val
                auto it = kick[node].lower_bound(mp(val + 1, -1));
                while(it != kick[node].begin()){
                    it -- ;
                    lis.push_back(it->se);
                    it = kick[node].erase(it);
                }
            }
            else{
                auto it = kick[node].lower_bound(mp(val, -1));
                while(it != kick[node].end()){
                    lis.push_back(it->se);
                    it = kick[node].erase(it);
                }
            }
            return;
        }
        int mid = (cl + cr) / 2;
        get(node * 2, cl, mid, tl, tr, val, mode);
        get(node * 2 + 1, mid + 1, cr, tl, tr, val, mode);

    }
};

segm t1, t2;

int main(){
    fastIO;
    int n, m;
    cin >> n >> m;
    vector<pii> zz;
    for(int i = 1; i <= m; i ++ ){
        cin >> T[i] >> L[i] >> R[i] >> C[i];
        zz.push_back(mp(T[i], i));
    }
    sort(zz.begin(), zz.end());
    for(int i = 0 ; i < m ; i ++ ){
        t1.ins(1, 0, m - 1, i, T[zz[i].se] + L[zz[i].se],zz[i].se);
        t2.ins(1, 0, m - 1, i, L[zz[i].se] - 1 - T[zz[i].se],zz[i].se);
    }
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for(int i = 1; i <= m ; i ++ ){
        dist[i] = inf;
        if(L[i] == 1){
            dist[i] = C[i];
            pq.push(mp(C[i], i));
        }
    }
    int id;
    ll outp = inf;
    int idx;
    while(!pq.empty()){
        id = pq.top().se;
        pq.pop();
        if(R[id] == n){
            outp = min(outp, dist[id]);
        }
        idx = lower_bound(zz.begin(), zz.end(), mp(T[id], -1)) - zz.begin();
        lis.clear();
        t1.get(1, 0, m - 1, idx, m - 1, R[id] + 1 + T[id],0);
        t2.get(1, 0, m - 1, 0, idx - 1, R[id] - T[id], 0);
        for(auto x : lis){
            if(dist[x] == inf){
                dist[x] = dist[id] + C[x];
                pq.push(mp(dist[x], x));
            }
        }
    }
    if(outp == inf)
        cout << "-1\n";
    else
        cout << outp << "\n";
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1483 ms 264992 KB Output is correct
2 Correct 1469 ms 268064 KB Output is correct
3 Correct 1806 ms 268828 KB Output is correct
4 Correct 1825 ms 268276 KB Output is correct
5 Correct 1630 ms 271072 KB Output is correct
6 Correct 1365 ms 268296 KB Output is correct
7 Correct 1146 ms 268220 KB Output is correct
8 Correct 1595 ms 268084 KB Output is correct
9 Correct 1368 ms 267948 KB Output is correct
10 Correct 1126 ms 268024 KB Output is correct
11 Correct 1984 ms 271928 KB Output is correct
12 Correct 1967 ms 272048 KB Output is correct
13 Correct 1982 ms 271208 KB Output is correct
14 Correct 1992 ms 271048 KB Output is correct
15 Correct 1447 ms 268056 KB Output is correct
16 Correct 1472 ms 268088 KB Output is correct
17 Correct 1464 ms 267384 KB Output is correct
18 Correct 1972 ms 271316 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 37964 KB Output is correct
2 Correct 20 ms 37872 KB Output is correct
3 Correct 21 ms 37964 KB Output is correct
4 Correct 21 ms 37984 KB Output is correct
5 Correct 21 ms 37868 KB Output is correct
6 Correct 21 ms 37908 KB Output is correct
7 Correct 22 ms 37968 KB Output is correct
8 Correct 21 ms 37960 KB Output is correct
9 Correct 21 ms 37964 KB Output is correct
10 Correct 21 ms 37980 KB Output is correct
11 Correct 20 ms 37964 KB Output is correct
12 Correct 20 ms 37904 KB Output is correct
13 Correct 21 ms 37968 KB Output is correct
14 Correct 21 ms 37856 KB Output is correct
15 Correct 21 ms 37964 KB Output is correct
16 Correct 20 ms 37964 KB Output is correct
17 Correct 20 ms 37964 KB Output is correct
18 Correct 21 ms 37880 KB Output is correct
19 Correct 21 ms 37876 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 37964 KB Output is correct
2 Correct 20 ms 37872 KB Output is correct
3 Correct 21 ms 37964 KB Output is correct
4 Correct 21 ms 37984 KB Output is correct
5 Correct 21 ms 37868 KB Output is correct
6 Correct 21 ms 37908 KB Output is correct
7 Correct 22 ms 37968 KB Output is correct
8 Correct 21 ms 37960 KB Output is correct
9 Correct 21 ms 37964 KB Output is correct
10 Correct 21 ms 37980 KB Output is correct
11 Correct 20 ms 37964 KB Output is correct
12 Correct 20 ms 37904 KB Output is correct
13 Correct 21 ms 37968 KB Output is correct
14 Correct 21 ms 37856 KB Output is correct
15 Correct 21 ms 37964 KB Output is correct
16 Correct 20 ms 37964 KB Output is correct
17 Correct 20 ms 37964 KB Output is correct
18 Correct 21 ms 37880 KB Output is correct
19 Correct 21 ms 37876 KB Output is correct
20 Correct 61 ms 46648 KB Output is correct
21 Correct 61 ms 46648 KB Output is correct
22 Correct 61 ms 46648 KB Output is correct
23 Correct 52 ms 46480 KB Output is correct
24 Correct 66 ms 46608 KB Output is correct
25 Correct 62 ms 46532 KB Output is correct
26 Correct 63 ms 46516 KB Output is correct
27 Correct 61 ms 46588 KB Output is correct
28 Correct 65 ms 46664 KB Output is correct
29 Correct 60 ms 46608 KB Output is correct
30 Correct 50 ms 46600 KB Output is correct
31 Correct 48 ms 46532 KB Output is correct
32 Correct 64 ms 46748 KB Output is correct
33 Correct 63 ms 46848 KB Output is correct
34 Correct 69 ms 46532 KB Output is correct
35 Correct 66 ms 46788 KB Output is correct
36 Correct 62 ms 46812 KB Output is correct
37 Correct 65 ms 46536 KB Output is correct

Subtask #4
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 1483 ms 264992 KB Output is correct
2 Correct 1469 ms 268064 KB Output is correct
3 Correct 1806 ms 268828 KB Output is correct
4 Correct 1825 ms 268276 KB Output is correct
5 Correct 1630 ms 271072 KB Output is correct
6 Correct 1365 ms 268296 KB Output is correct
7 Correct 1146 ms 268220 KB Output is correct
8 Correct 1595 ms 268084 KB Output is correct
9 Correct 1368 ms 267948 KB Output is correct
10 Correct 1126 ms 268024 KB Output is correct
11 Correct 1984 ms 271928 KB Output is correct
12 Correct 1967 ms 272048 KB Output is correct
13 Correct 1982 ms 271208 KB Output is correct
14 Correct 1992 ms 271048 KB Output is correct
15 Correct 1447 ms 268056 KB Output is correct
16 Correct 1472 ms 268088 KB Output is correct
17 Correct 1464 ms 267384 KB Output is correct
18 Correct 1972 ms 271316 KB Output is correct
19 Correct 20 ms 37964 KB Output is correct
20 Correct 20 ms 37872 KB Output is correct
21 Correct 21 ms 37964 KB Output is correct
22 Correct 21 ms 37984 KB Output is correct
23 Correct 21 ms 37868 KB Output is correct
24 Correct 21 ms 37908 KB Output is correct
25 Correct 22 ms 37968 KB Output is correct
26 Correct 21 ms 37960 KB Output is correct
27 Correct 21 ms 37964 KB Output is correct
28 Correct 21 ms 37980 KB Output is correct
29 Correct 20 ms 37964 KB Output is correct
30 Correct 20 ms 37904 KB Output is correct
31 Correct 21 ms 37968 KB Output is correct
32 Correct 21 ms 37856 KB Output is correct
33 Correct 21 ms 37964 KB Output is correct
34 Correct 20 ms 37964 KB Output is correct
35 Correct 20 ms 37964 KB Output is correct
36 Correct 21 ms 37880 KB Output is correct
37 Correct 21 ms 37876 KB Output is correct
38 Correct 61 ms 46648 KB Output is correct
39 Correct 61 ms 46648 KB Output is correct
40 Correct 61 ms 46648 KB Output is correct
41 Correct 52 ms 46480 KB Output is correct
42 Correct 66 ms 46608 KB Output is correct
43 Correct 62 ms 46532 KB Output is correct
44 Correct 63 ms 46516 KB Output is correct
45 Correct 61 ms 46588 KB Output is correct
46 Correct 65 ms 46664 KB Output is correct
47 Correct 60 ms 46608 KB Output is correct
48 Correct 50 ms 46600 KB Output is correct
49 Correct 48 ms 46532 KB Output is correct
50 Correct 64 ms 46748 KB Output is correct
51 Correct 63 ms 46848 KB Output is correct
52 Correct 69 ms 46532 KB Output is correct
53 Correct 66 ms 46788 KB Output is correct
54 Correct 62 ms 46812 KB Output is correct
55 Correct 65 ms 46536 KB Output is correct
56 Correct 1738 ms 269544 KB Output is correct
57 Correct 1770 ms 269800 KB Output is correct
58 Correct 1642 ms 267832 KB Output is correct
59 Correct 1647 ms 268040 KB Output is correct
60 Correct 1787 ms 269180 KB Output is correct
61 Correct 1589 ms 267764 KB Output is correct
62 Correct 1731 ms 269324 KB Output is correct
63 Correct 1711 ms 269244 KB Output is correct
64 Correct 1714 ms 269172 KB Output is correct
65 Correct 1432 ms 268432 KB Output is correct
66 Correct 1239 ms 268344 KB Output is correct
67 Correct 2406 ms 269244 KB Output is correct
68 Correct 2283 ms 269244 KB Output is correct
69 Correct 2001 ms 269060 KB Output is correct
70 Correct 2491 ms 269288 KB Output is correct
71 Correct 2277 ms 269316 KB Output is correct
72 Correct 1980 ms 268948 KB Output is correct
73 Correct 2492 ms 269112 KB Output is correct
74 Correct 1348 ms 269056 KB Output is correct
75 Correct 1176 ms 268856 KB Output is correct
76 Correct 2079 ms 272472 KB Output is correct
77 Correct 2181 ms 272708 KB Output is correct
78 Correct 2336 ms 271660 KB Output is correct
79 Correct 2518 ms 269484 KB Output is correct
80 Correct 2443 ms 268892 KB Output is correct
81 Correct 1441 ms 268984 KB Output is correct
82 Correct 2454 ms 268700 KB Output is correct
83 Correct 2497 ms 268952 KB Output is correct
84 Correct 2487 ms 268236 KB Output is correct
85 Correct 2087 ms 268988 KB Output is correct
86 Correct 2117 ms 268924 KB Output is correct
87 Correct 2177 ms 269136 KB Output is correct
88 Correct 1759 ms 269344 KB Output is correct
89 Correct 2151 ms 268892 KB Output is correct
90 Correct 2140 ms 272796 KB Output is correct
91 Correct 2375 ms 270920 KB Output is correct
92 Correct 2242 ms 269180 KB Output is correct
93 Correct 2513 ms 269044 KB Output is correct
94 Correct 2223 ms 269224 KB Output is correct
95 Correct 2348 ms 268764 KB Output is correct
96 Correct 2308 ms 272624 KB Output is correct
97 Correct 2162 ms 272720 KB Output is correct
98 Correct 2209 ms 272912 KB Output is correct
99 Correct 2190 ms 272568 KB Output is correct
100 Correct 2036 ms 272688 KB Output is correct
101 Correct 2147 ms 272592 KB Output is correct
102 Correct 2001 ms 273464 KB Output is correct
103 Correct 2265 ms 269376 KB Output is correct