Submission #423915

#	Time	Username	Problem	Language	Result	Execution time	Memory
423915		jamezzz	Treatment Project (JOI20_treatment)	C++17	0 / 100	3040 ms	18880 KiB

treatment

#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define LINF 1023456789123456789
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,int> li;

#define maxn 200005

int n,m,t[maxn],l[maxn],r[maxn],c[maxn];
ll dist[maxn];
vector<int> d;
vector<ii> AL[maxn];
priority_queue<ii,vector<ii>,greater<ii>> pq;

int main(){
	sf("%d%d",&n,&m);
	d.pb(1);d.pb(n+1);
	for(int i=0;i<m;++i){
		sf("%d%d%d%d",&t[i],&l[i],&r[i],&c[i]);
		d.pb(l[i]);d.pb(r[i]+1);
	}
	sort(all(d));
	d.erase(unique(all(d)),d.end());
	for(int i=0;i<m;++i){
		l[i]=lower_bound(all(d),l[i])-d.begin();
		r[i]=lower_bound(all(d),r[i]+1)-d.begin();
		AL[l[i]].pb(r[i],c[i]);
	}
	n=d.size();
	for(int i=0;i<n;++i){
		dist[i]=LINF;
		if(i!=0)AL[i].pb(i-1,0);
	}
	dist[0]=0;
	pq.push(li(0,0));
	while(!pq.empty()){
		ll d;int u;tie(d,u)=pq.top();pq.pop();
		if(d>dist[u])continue;
		for(ii pr:AL[u]){
			if(dist[pr.fi]>dist[u]+pr.se){
				dist[pr.fi]=dist[u]+pr.se;
				pq.push(li(dist[pr.fi],pr.fi));
			}
		}
	}
	if(dist[n-1]==LINF)pf("-1\n");
	else pf("%lld\n",dist[n-1]);
}

/*
10 5
1 5 10 3
1 1 6 5
1 2 8 3
1 6 10 4
1 1 3 1
*/

Compilation message (stderr)

treatment.cpp: In function 'int main()':
treatment.cpp:24:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  sf("%d%d",&n,&m);
      |    ^
treatment.cpp:27:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   sf("%d%d%d%d",&t[i],&l[i],&r[i],&c[i]);
      |     ^

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