oj.uz

Submission #682838

# Submission time Handle Problem Language Result Execution time Memory
682838 2023-01-17T05:50:01 Z Evirir Treatment Project (JOI20_treatment) C++17
100 / 100
 1060 ms 284428 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define cbug if(DEBUG) cout
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
//template<typename T>
//using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
ostream& operator<<(ostream &out, ii x){ out<<"("<<x.F<<","<<x.S<<")"; return out; }
template<typename T> void amax(T &a, T b){ a=max(a,b); }
template<typename T> void amin(T &a, T b){ a=min(a,b); }
const ll INF = ll(1e18);
const int MOD = 998244353;

struct Project
{
    ll t, l, r, cost;
};

istream& operator>>(istream& in, Project &p)
{
    in >> p.t >> p.l >> p.r >> p.cost;
    p.l--;
    p.r--;
    return in;
}

ll n;
int m;
vector<Project> projects;
vector<ll> dist;
vector<ll> l_plus_t, l_minus_t, times;        // list of all values
vector<ll> c_times;  // idx to compressed
vector<vector<int>> plus_groups, minus_groups;
vector<bool> vst;

class PointSegmentTree{
private:
    bool at_least;
    int size_;
    vector<set<ii>> v;
    void build(const vector<vector<int>> &groups, int k, int l, int r)
    {
        if (l == r)
        {
            for (int id : groups[l])
            {
                v[k].insert({projects[id].t, id});
            }
            return;
        }
        int mid = (l + r) / 2;
        build(groups, k * 2, l, mid);
        build(groups, k * 2 + 1, mid + 1, r);
        v[k].insert(all(v[k * 2]));
        v[k].insert(all(v[k * 2 + 1]));
    }
    void query(int s, int e, ll curt, vector<int> &res, int k, int l, int r)
    {
        if(e < l || r < s) return;
        if(s <= l && r <= e)
        {
            while(!v[k].empty())
            {
                set<ii>::iterator it;
                if (at_least)
                {
                    it = --v[k].end();
                    if (it->first < curt) break;
                }
                else
                {
                    it = v[k].begin();
                    if (it->first >= curt) break;
                }
                int id = it->second;
                if (!vst[id])
                {
                    vst[id] = true;
                    res.push_back(id);
                }
                v[k].erase(it);
            }
            return;
        }
        int mid = (l + r) >> 1;
        query(s, e, curt, res, k*2, l, mid);
        query(s, e, curt, res, k*2+1, mid+1, r);
    }

public:
    PointSegmentTree(int n, bool at_least){
        size_ = n;
        v.resize(size_*4);
        this->at_least = at_least;
    }
    void build(const vector<vector<int>> &groups) {
        build(groups, 1, 0, size_ - 1);
    }
    vector<int> query(int l, int r, ll curt){
        vector<int> res;
        query(l, r, curt, res, 1, 0, size_-1);
        return res;
    }
};

void compress(vector<ll> &v)
{
    sort(v.begin(), v.end());
    v.erase(unique(all(v)), v.end());
}

int getCompressed(const vector<ll> &v, ll val)
{
    return upper_bound(all(v), val) - v.begin() - 1;
}

void computeCompressions()
{
    c_times.resize(m);
    for (const auto &p : projects)
    {
        l_plus_t.push_back(p.l + p.t);
        l_minus_t.push_back(p.l - p.t);
        times.push_back(p.t);
    }
    compress(l_plus_t);
    compress(l_minus_t);
    compress(times);

    plus_groups.resize(l_plus_t.size());
    minus_groups.resize(l_minus_t.size());
    forn(i,0,m)
    {
        const Project &p = projects[i];
        int plus_id = getCompressed(l_plus_t, p.l + p.t);
        int minus_id = getCompressed(l_minus_t, p.l - p.t);
        plus_groups[plus_id].pb(i);
        minus_groups[minus_id].pb(i);
        c_times[i] = getCompressed(times, p.t);
    }
}

void dijkstra()
{
    priority_queue<ii, vector<ii>, greater<ii>> q; // (distance, node)
    fill(dist.begin(), dist.end(), INF);

    computeCompressions();

    PointSegmentTree st_plus(l_plus_t.size(), true);
    PointSegmentTree st_minus(l_minus_t.size(), false);
    st_plus.build(plus_groups);
    st_minus.build(minus_groups);

    // initial nodes
    for (int i = 0; i < m; i++)
    {
        auto p = projects[i];
        if (p.l != 0) continue;
        dist[i] = p.cost;
        vst[i] = true;
        q.push({dist[i], i});
    }

    // dijkstra loop
    while (!q.empty())
    {
        auto [cur_dist, u] = q.top();
        q.pop();
        if (cur_dist > dist[u]) continue;
        const Project &p = projects[u];
        auto next_p = st_plus.query(0, getCompressed(l_plus_t, p.r + p.t + 1), p.t);
        auto next_minus = st_minus.query(0, getCompressed(l_minus_t, p.r - p.t + 1), p.t);
        next_p.insert(next_p.end(), all(next_minus));
        for (int id : next_p)
        {
            dist[id] = cur_dist + projects[id].cost;
            q.push({dist[id], id});
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    // freopen("test.in", "r", stdin);

    cin >> n >> m;
    vst.resize(m, false);
    projects.resize(m);
    dist.resize(m);
    forn(i, 0, m) cin >> projects[i];
    dijkstra();

    ll ans = INF;
    forn(i, 0, m)
    {
        if (projects[i].r == n - 1)
        {
            ans = min(ans, dist[i]);
        }
    }

    if (ans == INF) ans = -1;
    cout << ans << '\n';

    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 277492 KB Output is correct
2 Correct 659 ms 277516 KB Output is correct
3 Correct 706 ms 244064 KB Output is correct
4 Correct 723 ms 244072 KB Output is correct
5 Correct 365 ms 108032 KB Output is correct
6 Correct 431 ms 149416 KB Output is correct
7 Correct 587 ms 196140 KB Output is correct
8 Correct 335 ms 107956 KB Output is correct
9 Correct 402 ms 149428 KB Output is correct
10 Correct 566 ms 196248 KB Output is correct
11 Correct 751 ms 282120 KB Output is correct
12 Correct 851 ms 281196 KB Output is correct
13 Correct 886 ms 280704 KB Output is correct
14 Correct 896 ms 280532 KB Output is correct
15 Correct 750 ms 280564 KB Output is correct
16 Correct 722 ms 280492 KB Output is correct
17 Correct 712 ms 279692 KB Output is correct
18 Correct 800 ms 281648 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 284 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 320 KB Output is correct
18 Correct 1 ms 316 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 27 ms 11136 KB Output is correct
21 Correct 27 ms 11220 KB Output is correct
22 Correct 38 ms 11604 KB Output is correct
23 Correct 27 ms 11648 KB Output is correct
24 Correct 35 ms 11804 KB Output is correct
25 Correct 30 ms 11668 KB Output is correct
26 Correct 32 ms 11596 KB Output is correct
27 Correct 36 ms 11596 KB Output is correct
28 Correct 32 ms 11772 KB Output is correct
29 Correct 32 ms 11628 KB Output is correct
30 Correct 23 ms 11696 KB Output is correct
31 Correct 23 ms 11596 KB Output is correct
32 Correct 30 ms 11848 KB Output is correct
33 Correct 28 ms 11784 KB Output is correct
34 Correct 30 ms 11600 KB Output is correct
35 Correct 31 ms 11784 KB Output is correct
36 Correct 29 ms 11724 KB Output is correct
37 Correct 31 ms 11596 KB Output is correct

Subtask #4
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 277492 KB Output is correct
2 Correct 659 ms 277516 KB Output is correct
3 Correct 706 ms 244064 KB Output is correct
4 Correct 723 ms 244072 KB Output is correct
5 Correct 365 ms 108032 KB Output is correct
6 Correct 431 ms 149416 KB Output is correct
7 Correct 587 ms 196140 KB Output is correct
8 Correct 335 ms 107956 KB Output is correct
9 Correct 402 ms 149428 KB Output is correct
10 Correct 566 ms 196248 KB Output is correct
11 Correct 751 ms 282120 KB Output is correct
12 Correct 851 ms 281196 KB Output is correct
13 Correct 886 ms 280704 KB Output is correct
14 Correct 896 ms 280532 KB Output is correct
15 Correct 750 ms 280564 KB Output is correct
16 Correct 722 ms 280492 KB Output is correct
17 Correct 712 ms 279692 KB Output is correct
18 Correct 800 ms 281648 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 316 KB Output is correct
22 Correct 1 ms 320 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 1 ms 284 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 320 KB Output is correct
36 Correct 1 ms 316 KB Output is correct
37 Correct 0 ms 340 KB Output is correct
38 Correct 27 ms 11136 KB Output is correct
39 Correct 27 ms 11220 KB Output is correct
40 Correct 38 ms 11604 KB Output is correct
41 Correct 27 ms 11648 KB Output is correct
42 Correct 35 ms 11804 KB Output is correct
43 Correct 30 ms 11668 KB Output is correct
44 Correct 32 ms 11596 KB Output is correct
45 Correct 36 ms 11596 KB Output is correct
46 Correct 32 ms 11772 KB Output is correct
47 Correct 32 ms 11628 KB Output is correct
48 Correct 23 ms 11696 KB Output is correct
49 Correct 23 ms 11596 KB Output is correct
50 Correct 30 ms 11848 KB Output is correct
51 Correct 28 ms 11784 KB Output is correct
52 Correct 30 ms 11600 KB Output is correct
53 Correct 31 ms 11784 KB Output is correct
54 Correct 29 ms 11724 KB Output is correct
55 Correct 31 ms 11596 KB Output is correct
56 Correct 791 ms 271868 KB Output is correct
57 Correct 816 ms 272284 KB Output is correct
58 Correct 754 ms 279536 KB Output is correct
59 Correct 748 ms 279988 KB Output is correct
60 Correct 809 ms 280812 KB Output is correct
61 Correct 742 ms 279576 KB Output is correct
62 Correct 788 ms 271952 KB Output is correct
63 Correct 690 ms 280688 KB Output is correct
64 Correct 695 ms 280692 KB Output is correct
65 Correct 704 ms 280960 KB Output is correct
66 Correct 756 ms 280964 KB Output is correct
67 Correct 1020 ms 281548 KB Output is correct
68 Correct 858 ms 281356 KB Output is correct
69 Correct 764 ms 281296 KB Output is correct
70 Correct 1018 ms 281552 KB Output is correct
71 Correct 832 ms 281440 KB Output is correct
72 Correct 730 ms 281344 KB Output is correct
73 Correct 998 ms 281556 KB Output is correct
74 Correct 589 ms 281328 KB Output is correct
75 Correct 588 ms 281268 KB Output is correct
76 Correct 802 ms 282604 KB Output is correct
77 Correct 837 ms 283500 KB Output is correct
78 Correct 901 ms 283132 KB Output is correct
79 Correct 976 ms 281312 KB Output is correct
80 Correct 772 ms 281076 KB Output is correct
81 Correct 660 ms 281328 KB Output is correct
82 Correct 859 ms 280516 KB Output is correct
83 Correct 887 ms 280528 KB Output is correct
84 Correct 1060 ms 280720 KB Output is correct
85 Correct 755 ms 281396 KB Output is correct
86 Correct 797 ms 281352 KB Output is correct
87 Correct 816 ms 281344 KB Output is correct
88 Correct 757 ms 264168 KB Output is correct
89 Correct 765 ms 281312 KB Output is correct
90 Correct 906 ms 283392 KB Output is correct
91 Correct 961 ms 281336 KB Output is correct
92 Correct 782 ms 281392 KB Output is correct
93 Correct 975 ms 281364 KB Output is correct
94 Correct 773 ms 246236 KB Output is correct
95 Correct 901 ms 281348 KB Output is correct
96 Correct 888 ms 283396 KB Output is correct
97 Correct 859 ms 284400 KB Output is correct
98 Correct 847 ms 284428 KB Output is correct
99 Correct 869 ms 284188 KB Output is correct
100 Correct 807 ms 250484 KB Output is correct
101 Correct 850 ms 283396 KB Output is correct
102 Correct 791 ms 283612 KB Output is correct
103 Correct 865 ms 281816 KB Output is correct