Submission #1052379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052379		hotboy2703	Treatment Project (JOI20_treatment)	C++17	100 / 100	465 ms	105420 KiB

treatment

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 1e5+100;
const ll INF = 1e18;
ll dp[MAXN];
struct treatment{
    ll t,l,r,c;
};
treatment a[MAXN];
vector <pll> tree1[MAXN*4],tree2[MAXN*4];
vector <ll> val_t;
void update(ll id,ll l,ll r,ll pos){
    if (val_t[l] > a[pos].t || val_t[r] < a[pos].t)return;
    tree1[id].push_back(MP(a[pos].l - a[pos].t,pos));
    tree2[id].push_back(MP(a[pos].l + a[pos].t,pos));   
    if (l == r){
        return;
    }
    ll mid = (l + r) >> 1;
    update(id<<1,l,mid,pos);
    update(id<<1|1,mid+1,r,pos);
}
void build(ll id,ll l,ll r){
    sort(tree1[id].begin(),tree1[id].end(),greater <>());
    sort(tree2[id].begin(),tree2[id].end(),greater <>());
    if (l != r){
        ll mid = (l + r) >> 1;
        build(id<<1,l,mid);
        build(id<<1|1,mid+1,r);
    }
}
vector <ll> all;
void get1(ll id,ll l,ll r,ll pos){
    if (val_t[l] > a[pos].t)return;
    if (val_t[r] <= a[pos].t){
        while (!tree1[id].empty() && tree1[id].back().fi <= a[pos].r - a[pos].t + 1){
            all.push_back(tree1[id].back().se);
            tree1[id].pop_back();
        }
        return;
    }
    ll mid = (l + r) >> 1;
    get1(id<<1,l,mid,pos);
    get1(id<<1|1,mid+1,r,pos);
}
void get2(ll id,ll l,ll r,ll pos){
    if (val_t[r] < a[pos].t)return;
    if (val_t[l] >= a[pos].t){
            while (!tree2[id].empty() && tree2[id].back().fi <= a[pos].r + a[pos].t + 1){
            all.push_back(tree2[id].back().se);
            tree2[id].pop_back();
        }
        return;
    }
    ll mid = (l + r) >> 1;
    get2(id<<1,l,mid,pos);
    get2(id<<1|1,mid+1,r,pos);
}
ll n,m;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n>>m;
    for (ll i = 1;i <= m;i ++){
        cin>>a[i].t>>a[i].l>>a[i].r>>a[i].c;
        val_t.push_back(a[i].t);
    }
    sort(val_t.begin(),val_t.end());
    val_t.resize(unique(val_t.begin(),val_t.end())-val_t.begin());
    val_t.insert(val_t.begin(),0);
    for (ll i = 1;i <= m;i ++)update(1,1,sz(val_t)-1,i);
    build(1,1,sz(val_t)-1);
    priority_queue <pll,vector <pll> ,greater <> > q;
    for (ll i = 1;i <= m;i ++){
        if (a[i].l == 1){dp[i] = a[i].c;q.push(MP(a[i].c,i));}
        else dp[i] = INF;
    }
    while (!q.empty()){
        ll u = q.top().se;
        q.pop();
        all.clear();
        get1(1,1,sz(val_t)-1,u);
        get2(1,1,sz(val_t)-1,u);
        for (auto v:all){
            // cout<<v<<
            if (dp[v] == INF){
                dp[v] = dp[u] + a[v].c;
                q.push(MP(dp[v],v));
            }
        }
    }
    ll ans = INF;
    for (ll i = 1;i <= m;i ++)if (a[i].r == n)ans = min(ans,dp[i]);
    if (ans == INF)ans = -1;
cout<<ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 61 / 61