Submission #216328

#	Time	Username	Problem	Language	Result	Execution time	Memory
216328		zscoder	Treatment Project (JOI20_treatment)	C++17	100 / 100	873 ms	70292 KiB

treatment

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

struct segment
{
	int t;
	int l,r;
	int cost;
	segment(int _t, int _l, int _r, int _cost): t(_t), l(_l), r(_r), cost(_cost){}
	bool operator < (const segment &s) const 
	{
		if(t!=s.t) return t<s.t;
		if(l!=s.l) return l<s.l;
		if(r!=s.r) return r<s.r;
		return cost<s.cost;
	}	
};

ll N; int n;
ll dist[333333];
vector<segment> vec;
vector<pair<int,int> > st[2][455555];
const ll INF = ll(1e18);
void add(int ty, int id, int l, int r, int pos, int nd)
{
	if(pos>=r||pos<l) return ;
	if(ty==0) st[ty][id].pb({vec[nd].l+vec[nd].t,nd});
	else st[ty][id].pb({vec[nd].l-vec[nd].t,nd});
	if(r-l<2) return ;
	int mid=(l+r)>>1;
	add(ty,id*2,l,mid,pos,nd); add(ty,id*2+1,mid,r,pos,nd);
}

void getnodes(int ty, int id, int l, int r, int ql, int qr, int X, vi &nodes) //<= X
{
	if(ql>=r||l>=qr) return ;
	if(ql<=l&&r<=qr)
	{
		while(!st[ty][id].empty()&&st[ty][id].back().fi<=X)
		{
			nodes.pb(st[ty][id].back().se);
			st[ty][id].pop_back();
		}
		return ;
	}
	int mid=(l+r)>>1;
	getnodes(ty,id*2,l,mid,ql,qr,X,nodes);
	getnodes(ty,id*2+1,mid,r,ql,qr,X,nodes);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>N>>n;
	vector<int> Tcoord;
	for(int i=0;i<n;i++)
	{
		int t,l,r,c; cin>>t>>l>>r>>c; l--;
		vec.pb(segment(t,l,r,c));
		Tcoord.pb(t);
	}
	sort(Tcoord.begin(),Tcoord.end());
	Tcoord.erase(unique(Tcoord.begin(),Tcoord.end()),Tcoord.end());
	ll ans=ll(1e18);
	for(int i=0;i<n;i++)
	{
		dist[i]=ll(1e18);
		if(vec[i].l==0) continue;
		add(0,1,0,Tcoord.size(),lower_bound(Tcoord.begin(),Tcoord.end(),vec[i].t)-Tcoord.begin(),i);
		add(1,1,0,Tcoord.size(),lower_bound(Tcoord.begin(),Tcoord.end(),vec[i].t)-Tcoord.begin(),i);
	}
	for(int i=0;i<422222;i++)
	{
		for(int j=0;j<2;j++)
		{
			sort(st[j][i].rbegin(),st[j][i].rend());
		}
	}
	priority_queue<ii,vector<ii>,greater<ii> > pq;
	for(int i=0;i<n;i++)
	{
		if(vec[i].l==0)
		{
			pq.push({vec[i].cost,i});
			dist[i]=vec[i].cost;
		}
	}
	while(!pq.empty())
	{
		ii cur = pq.top(); pq.pop();
		int u = cur.se; ll d = cur.fi;
		int pos = lower_bound(Tcoord.begin(),Tcoord.end(),vec[u].t)-Tcoord.begin();
		vector<int> nodes;
		//T_j<T_i, search in st 1
		getnodes(1,1,0,Tcoord.size(),0,pos,vec[u].r-vec[u].t,nodes);
		//T_j>=T_i, search in st 0
		getnodes(0,1,0,Tcoord.size(),pos,Tcoord.size(),vec[u].r+vec[u].t,nodes);
		sort(nodes.begin(),nodes.end());
		nodes.erase(unique(nodes.begin(),nodes.end()),nodes.end());
		for(int x:nodes)
		{
			if(dist[x]>=INF)
			{
				dist[x]=min(dist[x],d+vec[x].cost);
				pq.push({dist[x],x});
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		if(vec[i].r==N)
		{
			ans=min(ans,dist[i]);
		}
	}
	if(ans>=ll(1e17)) ans=-1;
	cout<<ans<<'\n';
}

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