Submission #550258

#	Time	Username	Problem	Language	Result	Execution time	Memory
550258		Antekb	Treatment Project (JOI20_treatment)	C++14	100 / 100	513 ms	39572 KiB

treatment

#include<bits/stdc++.h>
#pragma GCC optimize("trapv")
#define st first
#define nd second
using namespace std;
using ll = long long;
const int N=1<<17;
const ll INF=1e18;
ll dist[N];
bool vis[N];
vector<pair<int, int> > tab[N+N];
vector<int> co;
vector<pair<pair<int, int>, pair<int, int>> > V;
set<pair<ll, int> > S;
void insert(int v, int val, int id){
	for(v+=N; v>1; v>>=1){
			//cout<<val<<" "<<id<<" "<<v<<"\n";
			tab[v].push_back({val, id});
	}
}
void find(ll d, int v, int val){
	for(v+=N; v>1; v>>=1){
		//cout<<"b\n";
		if(v&1){
			v--;
		//cout<<v<<"\n";
		while(tab[v].size() && tab[v].back().st<=val){
			int u=tab[v].back().nd;
			//cout<<u<<"a\n";
			//cout<<dist[u]<<" "<<d<<" "<<V[u].nd.nd<<"\n";
			if(dist[u]>d+V[u].nd.nd){
				//cout<<"c\n";
				//cout<<u<<"\n";
				//cout<<u<<" "<<d<<" "<<v<<"\n";
				//cout<<u<<" "<<V[u].st.st+V[u].nd.st<<" "<<V[u].st.st-V[u].nd.st<<"b\n";
				S.erase(S.find({dist[u], u}));
				dist[u]=d+V[u].nd.nd;
				S.insert({dist[u], u});
			}
			//cout<<u<<"a\n";
			tab[v].pop_back();
		}
		}
	}
}
int main(){
	int l, n;
	cin>>l>>n;
	V.resize(n);
	for(int i=0; i<n; ++i){
		cin>>V[i].nd.st>>V[i].st.st>>V[i].st.nd>>V[i].nd.nd;
		V[i].st.st--;
		co.push_back(V[i].st.st+V[i].nd.st);
	}
	sort(co.begin(), co.end());
	co.resize(unique(co.begin(), co.end())-co.begin());
	for(int i=0; i<n; i++){
		//cout<<i<<" "<<V[i].st.st+V[i].nd.st<<" "<<lower_bound(co.begin(), co.end(), V[i].st.st+V[i].nd.st)-co.begin()<<"\n";
		insert(lower_bound(co.begin(), co.end(), V[i].st.st+V[i].nd.st)
			-co.begin(), V[i].st.st-V[i].nd.st, i);
	}
	for(int i=0; i<N+N; i++){
		if(tab[i].size()){
			sort(tab[i].begin(), tab[i].end());
			reverse(tab[i].begin(), tab[i].end());
		}
	}
	for(int i=0; i<n; i++){
		if(V[i].st.st)dist[i]=INF;
		else dist[i]=V[i].nd.nd;
		S.insert({dist[i], i});
	}
	for(int ii=0; ii<n; ii++){
		int opt=S.begin()->nd;
		//cout<<opt<<" "<<dist[opt]<<"\n";
		//cout<<opt<<" "<<S.begin()->st<<"\n";
		S.erase(S.begin());
		if(V[opt].st.nd==l && dist[opt]!=INF){
			cout<<dist[opt];
			return 0;
		}
		//cout<<opt<<"\n";
		//cout<<V[opt].st.nd+V[opt].nd.st <<" "<<V[opt].st.nd-V[opt].nd.st <<"a\n";
		//cout<<opt<<" "<<upper_bound(co.begin(), co.end(), V[opt].st.nd+V[opt].nd.st)-co.begin()<<"\n";
		find(dist[opt], upper_bound(co.begin(), co.end(), V[opt].st.nd+V[opt].nd.st)
			-co.begin(), V[opt].st.nd-V[opt].nd.st);
		/*for(int i=0; i<n; i++){
			if(V[i].st.st+V[i].nd.st<=V[opt].st.nd+V[opt].nd.st 
				&& V[i].st.st-V[i].nd.st<=V[opt].st.nd-V[opt].nd.st){
				if(dist[i]>V[i].nd.nd+dist[opt]){
					dist[i]=V[i].nd.nd+dist[opt];
				}
			}
		}*/
	}
	cout<<-1;
}

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