Submission #765004

#	Time	Username	Problem	Language	Result	Execution time	Memory
765004		Dan4Life	Treatment Project (JOI20_treatment)	C++17	100 / 100	75 ms	6672 KiB

treatment

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

ll n, m, dis[mxM], seg[mxM*2];
struct Project{ int t, l, r, c; } a[mxM];
priority_queue<pii,vector<pii>,greater<pii>> pq;

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

void query(int i, int j, ll k, int p=0, int l=0, int r=m-1){
	if(i<a[l].l-a[l].t or j < seg[p]) return;
	if(l==r){
		if(dis[l]==LINF) dis[l] = k+a[l].c, pq.push({dis[l],l});
		seg[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);
	seg[p] = min(seg[p+1],seg[rp]);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	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){ return x.l-x.t < y.l-y.t; });
	fill(dis,dis+m,LINF); fill(seg,seg+2*m,LINF);
	for(int i = 0; i < m; i++) if(a[i].l==1)
		dis[i]=a[i].c, pq.push({a[i].c,i});
	bld();
	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);
	}
	ll ans = LINF;
	for(int i = 0; i < m; i++)
		if(a[i].r==n) ans=min(ans,dis[i]);
	cout << (ans==LINF?-1:ans);
}

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