Submission #241693

#	Time	Username	Problem	Language	Result	Execution time	Memory
241693		AMO5	Treatment Project (JOI20_treatment)	C++98	100 / 100	248 ms	52100 KiB

treatment

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<ll,int>pli;
const ll INF=1e18;
const int mxn=1e5+5;

/* T_i<=T_j, L_j+T_j<=R_i+T_i
 * T_i>=T_j, L_j-T_j<=R_i-T_i
 * connect them with edge then perform Dij
 * start from 1 -> n, note that the citizen 1 and n only affected by citizen 2 and n-1 respectively
*/

struct st{
	int t,le,ri,cost;
	st(int t,int le, int ri, int cost):t(t),le(le),ri(ri),cost(cost){};
};

struct point{
	int m, p, ind;
	point(int m, int p, int ind):m(m),p(p),ind(ind){};
	bool operator < (const point &r)const {
		return m<r.m;
	}
};

struct node{
	int ind; ll d;
	bool operator < (const node &r) const {
		return d>r.d;
	}
};

vector<st>str;
vector<point>pt;
vector<pli>tree[mxn*4];
bool vis[mxn];

void build(int id, int le, int ri){
	if(le==ri){
		tree[id].eb(pt[le].p,pt[le].ind);
	}else{
		int mid=(le+ri)/2;
		build(id*2,le,mid);
		build(id*2+1,mid+1,ri);
		tree[id].resize(tree[id*2].size()+tree[id*2+1].size());
		merge(all(tree[id*2]),all(tree[id*2+1]),tree[id].begin(),greater<pli>());
	}
	return;
}

void getnodes(int pos, int val, int id, int le, int ri, vi &v){
	if(le>=pos)return;
	if(ri<pos){
		while(!tree[id].empty()&&tree[id].back().fi<=val){
			//fi = point.p = le+t, val = ri+t, le+t<=ri+t for t_i<=t_j
			int ind = tree[id].back().se;
			if(!vis[ind])v.eb(ind);
			tree[id].pop_back();
		}
		return;
	}
	int mid=(le+ri)/2;
	getnodes(pos,val,id*2,le,mid,v);
	getnodes(pos,val,id*2+1,mid+1,ri,v);
	return;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int n,m; cin >> n >> m;
	int t,le,ri,cost;
	for(int i=0; i<m; i++){
		cin >> t >> le >> ri >> cost;
		str.eb(t,le,ri,cost);
		pt.eb(le-t,le+t,i);
	}
	sort(all(pt));
	build(1,0,m-1);
	/*
	for(int i=0; i<m; i++){
		cout << i << ' ' << pt[i].m << ' ' << pt[i].p << ' ' << pt[i].ind << '\n';
	}
	*/ 
	ll dist[m];
	for(int i=0; i<m; i++)dist[i]=INF,vis[i]=0;
	priority_queue<node>pq;
	for(int i=0; i<m; i++){
		if(str[i].le==1){
			vis[i]=1;
			dist[i]=(ll)str[i].cost;
			pq.push({i,dist[i]});
		}
	}
	while(!pq.empty()){
		int u = pq.top().ind;
		pq.pop();
		vi vt;
		int pos = lower_bound(all(pt),point(str[u].ri-str[u].t+2,-1,-1))-pt.begin();
		int val = str[u].ri+str[u].t+1;
		getnodes(pos,val,1,0,m-1,vt);
		for(int v:vt){
			if(vis[v])continue;
			vis[v]=1;
			dist[v] = dist[u]+(ll)str[v].cost;
			pq.push({v,dist[v]});
		}
		 
	}
	
	ll ans = INF;
	for(int i=0; i<m; i++){
		if(str[i].ri==n){
			ans = min(ans,dist[i]);
		}
	}
	if(ans==INF)ans=-1;
	cout << ans << '\n';
}

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