Submission #706614

#	Time	Username	Problem	Language	Result	Execution time	Memory
706614		alvingogo	Treatment Project (JOI20_treatment)	C++14	100 / 100	1657 ms	170688 KiB

treatment

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

const int inf=1e18;

struct ST{
    vector<set<pair<int,int> > > st;
    void init(int x){
        st.resize(4*x);
    }
    void update(int v,int L,int R,int p,pair<int,int> k,int t){
        if(t>0){
            st[v].insert(k);
        }
        else{
            st[v].erase(st[v].find(k));
        }
        if(L==R){
            return;
        }
        int m=(L+R)/2;
        if(p<=m){
            update(2*v+1,L,m,p,k,t);
        }
        else{
            update(2*v+2,m+1,R,p,k,t);
        }
    }
    pair<int,int> query(int v,int L,int R,int p){
        if(L==R){
            if(st[v].size()){
                return *st[v].begin();
            }
            else{
                return {inf,-1};
            }
        }
        int m=(L+R)/2;
        if(p<=m){
            return query(2*v+1,L,m,p);
        }
        else{
            pair<int,int> a,b=query(2*v+2,m+1,R,p);
            if(st[2*v+1].size()){
                a=*st[2*v+1].begin();
            }
            else{
                a={inf,-1};
            }
            return min(a,b);
        }
    }
}st;
signed main(){
    AquA;
    int n,m;
    cin >> m >> n;
    vector<int> cx(n),px,py,a(n),b(n);
    vector<pair<int,int> > vl(n),vr(n);
    for(int i=0;i<n;i++){
        int l,r,t,c;
        cin >> t >> l >> r >> c;
        a[i]=l;
        b[i]=r;
        vl[i]={l-t,l+t};
        vr[i]={r-t+1,r+t+1};
        px.push_back(vl[i].fs);
        px.push_back(vr[i].fs);
        py.push_back(vl[i].sc);
        py.push_back(vr[i].sc);
        // vl[l] to node <= vr[r]
        cx[i]=c;
    }
    sort(px.begin(),px.end());
    sort(py.begin(),py.end());
    px.erase(unique(px.begin(),px.end()),px.end());
    py.erase(unique(py.begin(),py.end()),py.end());
    int s=px.size();
    st.init(s);
    for(int i=0;i<n;i++){
        vl[i].fs=lower_bound(px.begin(),px.end(),vl[i].fs)-px.begin();
        vr[i].fs=lower_bound(px.begin(),px.end(),vr[i].fs)-px.begin();
        vl[i].sc=lower_bound(py.begin(),py.end(),vl[i].sc)-py.begin();
        vr[i].sc=lower_bound(py.begin(),py.end(),vr[i].sc)-py.begin();
        st.update(0,0,s-1,vl[i].fs,{vl[i].sc,i},1);
    }
    int ans=1e18;
    p_q<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
    for(int i=0;i<n;i++){
        if(a[i]==1){
            pq.push({cx[i],i});
            st.update(0,0,s-1,vl[i].fs,{vl[i].sc,i},-1);
        }
    }
    while(pq.size()){
        auto h=pq.top();
        //cout << h.fs << " " << h.sc << "\n";
        pq.pop();
        if(b[h.sc]==m){
            ans=min(ans,h.fs);
        }
        while(1){
            auto y=st.query(0,0,s-1,vr[h.sc].fs);
            if(y.sc==-1 || y.fs>vr[h.sc].sc){
                break;
            }
            st.update(0,0,s-1,vl[y.sc].fs,{vl[y.sc].sc,y.sc},-1);
            pq.push({h.fs+cx[y.sc],y.sc});
        }
    }
    if(ans>5e17){
        cout << -1 << "\n";
    }
    else{
        cout << ans << "\n";
    }
    return 0;
}

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