Submission #682893

#	Time	Username	Problem	Language	Result	Execution time	Memory
682893		vjudge1	Treatment Project (JOI20_treatment)	C++17	100 / 100	1076 ms	282120 KiB

treatment

#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 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 61 / 61