Submission #749130

#	Time	Username	Problem	Language	Result	Execution time	Memory
749130		Dan4Life	Treatment Project (JOI20_treatment)	C++17	100 / 100	96 ms	12076 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
const int mxM = (int)1e5+10;
const int LINF = (int)1e18;
using pii = pair<int,int>;

vector<pii> v;
int n, m, ans=LINF, dis[mxM];
struct Project{ int t, l, r, c; } a[mxM];
priority_queue<pii,vector<pii>,greater<pii>> pq;
int segTree[mxM*2];

void upd(int x, int p=0, int l=0, int r=m-1){
	if(l==r){ segTree[p] = a[l].l+a[l].t; return; }
	int mid = (l+r)/2; int rp = p+2*(mid-l+1);
	if(x<=mid) upd(x,p+1,l,mid);
	else upd(x,rp,mid+1,r);
	segTree[p] = min(segTree[p+1],segTree[rp]);
}

void query(int i, int j, int k, int p=0, int l=0, int r=m-1){
	if(i<a[l].l-a[l].t or j < segTree[p]) return;
	if(l==r){
		if(dis[l]==LINF) dis[l] = k+a[l].c, pq.push({dis[l],l});
		segTree[p]=LINF; return;
	}
	int mid = (l+r)/2; int rp = p+2*(mid-l+1);
	query(i,j,k,p+1,l,mid); query(i,j,k,rp,mid+1,r);
	segTree[p] = min(segTree[p+1],segTree[rp]);
}

int dijkstra(vector<pii> v){
	fill(dis,dis+m,LINF);
	for(auto [u,w] : v) dis[u]=w, pq.push({w,u});
	for(int i = 0; i < m; i++) upd(i);
	while(!pq.empty()){
		auto [D,s] = pq.top(); pq.pop();
		query(a[s].r-a[s].t+1, a[s].r+a[s].t+1, D);
	}
	int d = LINF;
	for(int i = 0; i < m; i++) 
		if(a[i].r==n) d=min(d,dis[i]);
	return d;
}

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	fill(segTree,segTree+2*m,LINF);
	for(int i = 0; i < m; i++) 
		cin >> a[i].t >> a[i].l >> a[i].r >> a[i].c;
	sort(a,a+m,[&](Project x, Project y){
		if(x.l-x.t==y.l-y.t) return x.l+x.t < y.l+y.t;
		return x.l-x.t < y.l-y.t;
	});
	for(int i = 0; i < m; i++) 
		if(a[i].l==1) v.pb({i,a[i].c});
	ans = dijkstra(v); cout << (ans==LINF?-1:ans);
}

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