Submission #619893

#	Time	Username	Problem	Language	Result	Execution time	Memory
619893		CSQ31	Treatment Project (JOI20_treatment)	C++17	100 / 100	1398 ms	320724 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) a.size()
#define fi first
#define se second
#define all(a) a.begin(),a.end()
typedef long long int ll;
typedef pair<ll,ll> pii;
const int MAXN = 2e5+1;
ll t[MAXN],l[MAXN],r[MAXN],c[MAXN],dist[MAXN];
int tc[MAXN];
bool ded[MAXN];
vector<pii>adj[MAXN];
vector<int>crd,add[MAXN];
set<pii>s0[4*MAXN],s1[4*MAXN];
void build(int v,int L,int R){
	if(L==R){
		for(int x:add[L]){
			s0[v].insert({l[x] + t[x],x});
			s1[v].insert({l[x] - t[x],x});
		}
		return;
	}
	int tm = (L+R)/2;
	build(2*v,L,tm);
	build(2*v+1,tm+1,R);
	for(auto x:s0[2*v])s0[v].insert(x);
	for(auto x:s0[2*v+1])s0[v].insert(x);
	for(auto x:s1[2*v])s1[v].insert(x);
	for(auto x:s1[2*v+1])s1[v].insert(x);
}
vector<int>upd;
void query0(int v,int l,int r,int tl,int tr,int val){ //when t[i] > t[j]
	if(l>r)return;
	if(l==tl && r==tr){
		while(!s0[v].empty()){
			auto it = s0[v].upper_bound(make_pair(val,2e9));
			if(it==s0[v].begin())break;
			it--;
			if(ded[it->se]){
				s0[v].erase(it);
				continue;
			}else{
				ded[it->se] = 1;
				upd.pb(it->se);
				s0[v].erase(it);
			}
		}
		return;
	}
	int tm = (tl+tr)/2;
	query0(2*v,l,min(r,tm),tl,tm,val);
	query0(2*v+1,max(l,tm+1),r,tm+1,tr,val);
}
void query1(int v,int l,int r,int tl,int tr,int val){ //when t[i] > t[j]
	if(l>r)return;
	if(l==tl && r==tr){
		while(!s1[v].empty()){
			auto it = s1[v].upper_bound(make_pair(val,2e9));
			if(it==s1[v].begin())break;
			it--;
			if(ded[it->se]){
				s1[v].erase(it);
				continue;
			}else{
				ded[it->se] = 1;
				upd.pb(it->se);
				s1[v].erase(it);
			}
		}
		return;
	}
	int tm = (tl+tr)/2;
	query1(2*v,l,min(r,tm),tl,tm,val);
	query1(2*v+1,max(l,tm+1),r,tm+1,tr,val);
}
//ri >= lj + abs(t[i]-t[j])
//if t[i] > t[j]
//ri - t[i] >= lj - t[j]
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
int main()
{
	owo
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>t[i]>>l[i]>>r[i]>>c[i];
		crd.pb(t[i]);
		l[i]--;
	}
	sort(all(crd));
	crd.resize(unique(all(crd)) - crd.begin());
	int ss = sz(crd);
	for(int i=0;i<m;i++){
		tc[i] = lower_bound(all(crd),t[i]) - crd.begin();
		add[tc[i]].pb(i);
	}
	build(1,0,ss-1);
	//for(int i=0;i<m;i++)cout<<tc[i]<<" ";
	//cout<<'\n';
	priority_queue<pii,vector<pii>,greater<pii>>pq;
	for(int i=0;i<m;i++){
		dist[i] = 1e18;
		if(l[i] == 0){
			ded[i] = 1;
			dist[i] = c[i];
			pq.push({c[i],i});
		}
	}
	while(!pq.empty()){
		pii v = pq.top();
		//cout<<v.se<<'\n';
		pq.pop();
		upd.clear();
		query0(1,tc[v.se],ss-1,0,ss-1,r[v.se] + t[v.se]);
		query1(1,0,tc[v.se],0,ss-1,r[v.se] - t[v.se]);
		for(int x:upd){
			//cout<<v.se<<" "<<x<<'\n';
			if(dist[x] > dist[v.se] + c[x]){
				dist[x] = dist[v.se] + c[x];
				pq.push({dist[x],x});
			}
		}
	}
	ll ans = 1e18;
	for(int i=0;i<m;i++){
		if(r[i] == n)ans = min(ans,dist[i]);
	}
	if(ans==1e18)ans=-1;
	cout<<ans;
}

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