Submission #289611

#	Time	Username	Problem	Language	Result	Execution time	Memory
289611		TadijaSebez	Treatment Project (JOI20_treatment)	C++11	100 / 100	978 ms	51248 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
const int N=100050;
const ll inf=9e18;
struct project{
	int t,l,r,c;
	project(){}
	project(int a,int b,int d,int e):t(a),l(b),r(d),c(e){}
	bool operator < (project b){return l+r<b.l+b.r||(l+r==b.l+b.r&&t<b.t);}
}pro[N];
ll dist[N];
set<pair<int,int>> bit[N];
vector<pair<int,pii>> save;
vector<int> cor;
void AddPt(int x,int y,int idx){
	save.pb({idx,{x,y}});
	cor.pb(x);
}
int Find(int x){return lower_bound(cor.begin(),cor.end(),x)-cor.begin()+1;}
void AddBIT(int x,int y,int idx){
	//printf("Add %i %i %i\n",x,y,idx);
	x=Find(x);
	for(int i=x;i>=1;i-=i&-i)bit[i].insert({y,idx});
}
void DelBIT(int x,int y,int idx){
	//printf("Del %i %i %i\n",x,y,idx);
	x=Find(x);
	for(int i=x;i>=1;i-=i&-i)bit[i].erase({y,idx});
}
void Build(){
	sort(cor.begin(),cor.end());
	cor.erase(unique(cor.begin(),cor.end()),cor.end());
	for(auto o:save){
		AddBIT(o.second.first,o.second.second,o.first);
	}
}
int Get(pair<ll,pii> now){
	//printf("%lld %i %i\n",now.first,now.second.first,now.second.second);
	int x=Find(now.second.first);
	for(int i=x;i<=cor.size();i+=i&-i){
		auto it=bit[i].lower_bound({now.second.second,0});
		if(it!=bit[i].end())return it->second;
	}
	return 0;
}
int n,m;
int main(){
	scanf("%i %i",&n,&m);
	for(int i=1;i<=m;i++)scanf("%i %i %i %i",&pro[i].t,&pro[i].l,&pro[i].r,&pro[i].c);
	set<pair<ll,pii>> st;
	ll ans=inf;
	for(int i=1;i<=m;i++){
		if(pro[i].r==n){
			if(pro[i].l==1)ans=min(ans,(ll)pro[i].c);
			st.insert({pro[i].c,{pro[i].l+pro[i].t,pro[i].l-pro[i].t}});
		}else{
			AddPt(pro[i].r+1+pro[i].t,pro[i].r+1-pro[i].t,i);
		}
	}
	Build();
	while(st.size()){
		int u=Get(*st.begin());
		//printf("%i %lld\n",u,st.begin()->first);
		if(u==0){
			st.erase(st.begin());
			continue;
		}
		DelBIT(pro[u].r+1+pro[u].t,pro[u].r+1-pro[u].t,u);
		dist[u]=st.begin()->first+pro[u].c;
		//printf("%i %lld\n",u,dist[u]);
		if(pro[u].l==1)ans=min(ans,dist[u]);
		st.insert({dist[u],{pro[u].l+pro[u].t,pro[u].l-pro[u].t}});
	}
	printf("%lld\n",ans==inf?-1:ans);
	return 0;
}

Compilation message (stderr)

treatment.cpp: In function 'int Get(std::pair<long long int, std::pair<int, int> >)':
treatment.cpp:43:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i=x;i<=cor.size();i+=i&-i){
      |              ~^~~~~~~~~~~~
treatment.cpp: In function 'int main()':
treatment.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |  scanf("%i %i",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
treatment.cpp:52:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |  for(int i=1;i<=m;i++)scanf("%i %i %i %i",&pro[i].t,&pro[i].l,&pro[i].r,&pro[i].c);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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