Submission #420368

#	Time	Username	Problem	Language	Result	Execution time	Memory
420368		alishahali1382	Treatment Project (JOI20_treatment)	C++17	100 / 100	265 ms	13124 KiB

treatment

#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef pair<pii, int> piii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<" "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<" ";cerr<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) return cout<<x<<"\n", 0;
#define SZ(x) ((int)x.size())

const int inf=1000010000;
const ll INF=10000000000100000ll; // 1e16
const int mod=1000000007;
const int MAXN=100010;

int n, m, q, k, u, v, x, y, t;
int L[MAXN], R[MAXN], T[MAXN], C[MAXN];
int T2[MAXN];
int mark[MAXN];
ll dist[MAXN], ans=INF;
priority_queue<pll, vector<pll>, greater<pll>> pq;

inline bool upd(ll &x, ll y){
	if (x<=y) return 0;
	x=y;
	return 1;
}

struct Segment{
	pii seg[MAXN<<1];
	Segment(){
		fill(seg, seg+2*MAXN, pii(2*inf, 0));
	}
	void Set(int pos, pll val){
		for (seg[pos+=m]=val; pos>1; pos>>=1) seg[pos>>1]=min(seg[pos], seg[pos^1]);
	}
	pll Get(int l, int r){
		pii res=seg[0];
		for (l+=m, r+=m; l<r; l>>=1, r>>=1){
			if (l&1) res=min(res, seg[l++]);
			if (r&1) res=min(res, seg[--r]);
		}
		return res;
	}
} seg1, seg2;

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	memset(dist, 63, sizeof(dist));
	cin>>n>>m;
	vector<pii> comp;
	for (int i=1; i<=m; i++){
		cin>>T[i]>>L[i]>>R[i]>>C[i];
		L[i]--;
		comp.pb({T[i], i});
	}
	sort(all(comp));
	for (int i=0; i<m; i++) T2[comp[i].second]=i+1;
	for (int i=1; i<=m; i++){
		if (!L[i]) pq.push({dist[i]=C[i], i});
		else{
			seg1.Set(T2[i], {L[i]-T[i], i});
			seg2.Set(T2[i], {L[i]+T[i], i});
		}
	}
	while (pq.size()){
		int v=pq.top().second;
		pq.pop();
		while (1){
			int i=seg1.Get(1, T2[v]).second;
			if (!i || L[i]-T[i]>R[v]-T[v]) break ;
			seg1.Set(T2[i], seg1.seg[0]);
			seg2.Set(T2[i], seg1.seg[0]);
			pq.push({dist[i]=dist[v]+C[i], i});
		}
		while (1){
			int i=seg2.Get(T2[v], m+1).second;
			if (!i || L[i]+T[i]>R[v]+T[v]) break ;
			seg1.Set(T2[i], seg1.seg[0]);
			seg2.Set(T2[i], seg1.seg[0]);
			pq.push({dist[i]=dist[v]+C[i], i});
		}
	}
	for (int i=1; i<=m; i++) if (R[i]==n) upd(ans, dist[i]);
	if (ans>=INF) ans=-1;
	cout<<ans<<"\n";

	return 0;
}
/*
10 5
2 5 10 3
1 1 6 5
5 2 8 3
7 6 10 4
4 1 3 1

10 5
2 6 10 3
1 1 5 5
5 2 7 3
8 6 10 4
4 1 3 1

10 5
1 5 10 4
1 1 6 5
1 4 8 3
1 6 10 3
1 1 3 1


*/

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