oj.uz

Submission #682893

# Submission time Handle Problem Language Result Execution time Memory
682893 2023-01-17T07:56:44 Z vjudge1 Treatment Project (JOI20_treatment) C++17
100 / 100
 1076 ms 282120 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 715 ms 278580 KB Output is correct
2 Correct 661 ms 278048 KB Output is correct
3 Correct 661 ms 244628 KB Output is correct
4 Correct 654 ms 244620 KB Output is correct
5 Correct 340 ms 107476 KB Output is correct
6 Correct 422 ms 149012 KB Output is correct
7 Correct 584 ms 195764 KB Output is correct
8 Correct 300 ms 107572 KB Output is correct
9 Correct 429 ms 148968 KB Output is correct
10 Correct 556 ms 195700 KB Output is correct
11 Correct 766 ms 281476 KB Output is correct
12 Correct 848 ms 280440 KB Output is correct
13 Correct 916 ms 280088 KB Output is correct
14 Correct 890 ms 279816 KB Output is correct
15 Correct 751 ms 280040 KB Output is correct
16 Correct 753 ms 279992 KB Output is correct
17 Correct 734 ms 279892 KB Output is correct
18 Correct 730 ms 281572 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 320 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 224 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 320 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 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 212 KB Output is correct
19 Correct 0 ms 212 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 320 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 224 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 320 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 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 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 26 ms 11232 KB Output is correct
21 Correct 26 ms 11164 KB Output is correct
22 Correct 32 ms 11668 KB Output is correct
23 Correct 28 ms 11580 KB Output is correct
24 Correct 33 ms 11792 KB Output is correct
25 Correct 31 ms 11720 KB Output is correct
26 Correct 29 ms 11644 KB Output is correct
27 Correct 27 ms 11596 KB Output is correct
28 Correct 32 ms 11732 KB Output is correct
29 Correct 31 ms 11648 KB Output is correct
30 Correct 24 ms 11596 KB Output is correct
31 Correct 24 ms 11600 KB Output is correct
32 Correct 32 ms 11824 KB Output is correct
33 Correct 29 ms 11752 KB Output is correct
34 Correct 30 ms 11596 KB Output is correct
35 Correct 30 ms 11680 KB Output is correct
36 Correct 30 ms 11728 KB Output is correct
37 Correct 32 ms 11596 KB Output is correct

Subtask #4
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 715 ms 278580 KB Output is correct
2 Correct 661 ms 278048 KB Output is correct
3 Correct 661 ms 244628 KB Output is correct
4 Correct 654 ms 244620 KB Output is correct
5 Correct 340 ms 107476 KB Output is correct
6 Correct 422 ms 149012 KB Output is correct
7 Correct 584 ms 195764 KB Output is correct
8 Correct 300 ms 107572 KB Output is correct
9 Correct 429 ms 148968 KB Output is correct
10 Correct 556 ms 195700 KB Output is correct
11 Correct 766 ms 281476 KB Output is correct
12 Correct 848 ms 280440 KB Output is correct
13 Correct 916 ms 280088 KB Output is correct
14 Correct 890 ms 279816 KB Output is correct
15 Correct 751 ms 280040 KB Output is correct
16 Correct 753 ms 279992 KB Output is correct
17 Correct 734 ms 279892 KB Output is correct
18 Correct 730 ms 281572 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 320 KB Output is correct
21 Correct 0 ms 316 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 224 KB Output is correct
25 Correct 1 ms 320 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 0 ms 320 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 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 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 26 ms 11232 KB Output is correct
39 Correct 26 ms 11164 KB Output is correct
40 Correct 32 ms 11668 KB Output is correct
41 Correct 28 ms 11580 KB Output is correct
42 Correct 33 ms 11792 KB Output is correct
43 Correct 31 ms 11720 KB Output is correct
44 Correct 29 ms 11644 KB Output is correct
45 Correct 27 ms 11596 KB Output is correct
46 Correct 32 ms 11732 KB Output is correct
47 Correct 31 ms 11648 KB Output is correct
48 Correct 24 ms 11596 KB Output is correct
49 Correct 24 ms 11600 KB Output is correct
50 Correct 32 ms 11824 KB Output is correct
51 Correct 29 ms 11752 KB Output is correct
52 Correct 30 ms 11596 KB Output is correct
53 Correct 30 ms 11680 KB Output is correct
54 Correct 30 ms 11728 KB Output is correct
55 Correct 32 ms 11596 KB Output is correct
56 Correct 819 ms 271780 KB Output is correct
57 Correct 835 ms 272084 KB Output is correct
58 Correct 768 ms 279732 KB Output is correct
59 Correct 766 ms 279988 KB Output is correct
60 Correct 874 ms 280248 KB Output is correct
61 Correct 764 ms 279480 KB Output is correct
62 Correct 794 ms 271808 KB Output is correct
63 Correct 713 ms 280200 KB Output is correct
64 Correct 752 ms 280200 KB Output is correct
65 Correct 751 ms 280276 KB Output is correct
66 Correct 854 ms 280200 KB Output is correct
67 Correct 1027 ms 280372 KB Output is correct
68 Correct 827 ms 279824 KB Output is correct
69 Correct 761 ms 279976 KB Output is correct
70 Correct 1042 ms 280112 KB Output is correct
71 Correct 835 ms 279828 KB Output is correct
72 Correct 753 ms 279796 KB Output is correct
73 Correct 1037 ms 279908 KB Output is correct
74 Correct 599 ms 279792 KB Output is correct
75 Correct 592 ms 279768 KB Output is correct
76 Correct 812 ms 281556 KB Output is correct
77 Correct 853 ms 281780 KB Output is correct
78 Correct 889 ms 282120 KB Output is correct
79 Correct 969 ms 279864 KB Output is correct
80 Correct 768 ms 279932 KB Output is correct
81 Correct 682 ms 279704 KB Output is correct
82 Correct 908 ms 280024 KB Output is correct
83 Correct 896 ms 280288 KB Output is correct
84 Correct 1076 ms 280100 KB Output is correct
85 Correct 777 ms 279956 KB Output is correct
86 Correct 806 ms 279940 KB Output is correct
87 Correct 826 ms 279856 KB Output is correct
88 Correct 804 ms 262468 KB Output is correct
89 Correct 790 ms 279824 KB Output is correct
90 Correct 887 ms 281704 KB Output is correct
91 Correct 951 ms 279576 KB Output is correct
92 Correct 817 ms 279560 KB Output is correct
93 Correct 1020 ms 279608 KB Output is correct
94 Correct 802 ms 244360 KB Output is correct
95 Correct 897 ms 279488 KB Output is correct
96 Correct 888 ms 281564 KB Output is correct
97 Correct 873 ms 282056 KB Output is correct
98 Correct 867 ms 282016 KB Output is correct
99 Correct 837 ms 281908 KB Output is correct
100 Correct 825 ms 248188 KB Output is correct
101 Correct 843 ms 281104 KB Output is correct
102 Correct 770 ms 281268 KB Output is correct
103 Correct 850 ms 279224 KB Output is correct