Submission #1047847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047847		KiaRez	Treatment Project (JOI20_treatment)	C++17	35 / 100	298 ms	524288 KiB

treatment

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int M = 1e5+5, N = 3e5+23, lg = 17;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int m, n, par[N], L[N], R[N], t[N], p[N], seg[N];
ll c[N], d[N * 3 * lg], id=1, mark[N * 3 * lg];
vector<pll> adj[N * 3 * lg];
vector<int> comp[2];
bool cmp(int i, int j) {
    return (t[i] < t[j]);
}

void query(int v, int l, int r, int ind=1, int lc=1, int rc=(1<<lg)+1) {
    if(lc >= r) return;
    if(rc <= r) {
        adj[v].pb({seg[ind], 0}); return;
    }
    int mid = (lc+rc)/2;
    query(v, l, r, 2*ind, lc, mid);
    query(v, l, r, 2*ind+1, mid, rc);
}

void update(int ind, int v) {
    adj[id].pb({seg[ind], 0});
    adj[id].pb({v, c[v]});
    seg[ind] = id; 
    ind/=2; id++;
    while(ind > 0) {
        seg[ind] = id++;
        adj[seg[ind]].pb({seg[2*ind], 0});
        adj[seg[ind]].pb({seg[2*ind+1], 0});
        ind /= 2;
    }
}

int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>n>>m; id = m + 1;
    for(int i=1; i<=m; i++) {
        cin>>t[i]>>L[i]>>R[i]>>c[i];
        p[i] = i;
        comp[0].pb(L[i]-t[i]);
        comp[1].pb(L[i]+t[i]);
    }
    sort(p+1, p+m+1, cmp);

    for(int i=(1<<(lg + 1)); i>=1; i--) {
        seg[i] = id ++;
        if(i < (1<<lg)) {
            adj[seg[i]].pb({seg[2*i], 0});
            adj[seg[i]].pb({seg[2*i+1], 0});
        }
    }

    comp[0].pb(2e9); comp[1].pb(2e9);
sort(all(comp[0])); comp[0].resize(unique(all(comp[0]))-comp[0].begin());
sort(all(comp[1])); comp[1].resize(unique(all(comp[1]))-comp[1].begin());
    
    for(int i=1; i<=m; i++) {
        int ptr = lower_bound(all(comp[0]), R[p[i]]-t[p[i]]+2)-comp[0].begin();
        if(ptr != 0) {
            query(p[i], 1, ptr + 1);
        }
        ptr = lower_bound(all(comp[0]), L[p[i]]-t[p[i]])-comp[0].begin()+1;
        update((1<<lg)+ptr-1, p[i]);
    }

    // for(int i=1; i<=m; i++) {
    //     for(int j=1; j<i; j++) {
    //         if(L[p[j]]-t[p[j]]<=R[p[i]]-t[p[i]]+1) {
    //             cout<<i<<' '<<j<<endl;
    //             adj[p[i]].pb({p[j], c[p[j]]});
    //         }
    //     }
    // }

    for(int i=(1<<(lg + 1)); i>=1; i--) {
        seg[i] = id ++;
        if(i < (1<<lg)) {
            adj[seg[i]].pb({seg[2*i], 0});
            adj[seg[i]].pb({seg[2*i+1], 0});
        }
    }
    
    for(int i=m; i>=1; i--) {
        int ptr = lower_bound(all(comp[1]), R[p[i]]+t[p[i]]+2)-comp[1].begin();
        if(ptr != 0) {
            query(p[i], 1, ptr + 1);
        }
        ptr = lower_bound(all(comp[1]), L[p[i]]+t[p[i]])-comp[1].begin()+1;
        update((1<<lg)+ptr-1, p[i]);
    }

    // for(int i=1; i<=m; i++) {
    //     for(int j=i+1; j<=m; j++) {
    //         if(L[p[j]]+t[p[j]]<=R[p[i]]+t[p[i]]+1) {
    //             cout<<i<<' '<<j<<endl;
    //             adj[p[i]].pb({p[j], c[p[j]]});
    //         }
    //     }
    // }

    priority_queue<pll, vector<pll>, greater<pll>> pq;
    for(int i=1; i<=m; i++) {
        if(L[i] == 1) {
            pq.push({c[i], i});
        }
    }

    while(size(pq) > 0) {
        pll v = pq.top(); pq.pop(); 
        if(mark[v.S] == 1) continue;
        // fuck(v.S);

        d[v.S] = v.F, mark[v.S] = 1;
        for(auto u : adj[v.S]) {
            if(mark[u.F] == 1) continue;
            // d[u.F] = min(d[u.F], v.F+u.S);
            // if(d[u.F] == v.F + u.S) {
            //     par[u.F] = v.S;
                pq.push({v.F+u.S, u.F});
            // }
            // fuck(u.F);
        }
    }

    ll ans = 2e18;
    for(int i=1 ; i<=m; i++) {
        if(d[i] == 0) continue;
        if(R[i] == n) {
            ans = min(ans, d[i]);
        }
    }

    cout<<(ans==2e18 ? -1 : ans)<<endl;

	return 0;
}

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