Submission #408678

#	Time	Username	Problem	Language	Result	Execution time	Memory
408678		doowey	Treatment Project (JOI20_treatment)	C++14	100 / 100	2518 ms	273464 KiB

treatment

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