Submission #445908

#	Time	Username	Problem	Language	Result	Execution time	Memory
445908		kig9981	Treatment Project (JOI20_treatment)	C++17	0 / 100	3083 ms	239848 KiB

treatment

#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;
 
const long long INF=0x3f3f3f3f3f3f3f3fLL;
const int SZ=1<<18;
set<pair<int,int>> xtree[2*SZ], ytree[2*SZ];
vector<int> P, x, y;
vector<tuple<int,int,int,int,int>> A;
long long dist[100000];
int chk[100000];

void set_tree(set<pair<int,int>> *tree, int s, int e, int p1, int p2, int i)
{
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) {
			tree[s].emplace(p1,i);
			tree[s++].emplace(p2,i);
		}
		if(~e&1) {
			tree[e].emplace(p1,i);
			tree[e--].emplace(p2,i);
		}
	}
}

void erase_tree(set<pair<int,int>> *tree, int s, int e, int p1, int p2, int i)
{
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) {
			tree[s].erase({p1,i});
			tree[s++].erase({p2,i});
		}
		if(~e&1) {
			tree[e].erase({p1,i});
			tree[e--].erase({p2,i});
		}
	}
}

void get_pos(set<pair<int,int>> *tree, int s, int e, int l, int r)
{
	for(int n=s+SZ;n;n>>=1) for(auto L=tree[n].lower_bound({l,0}),R=tree[n].lower_bound({r+1,0});L!=R;++L) P.push_back(L->second);
	for(int n=e+SZ;n;n>>=1) for(auto L=tree[n].lower_bound({l,0}),R=tree[n].lower_bound({r+1,0});L!=R;++L) P.push_back(L->second);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M;
	priority_queue<pair<long long,int>> Q;
	long long ans;
	cin>>N>>M; A.resize(M);
	memset(dist,0x3f,sizeof(dist));
	for(int i=0;i<M;i++) {
		auto &[t,l,r,aa,c]=A[i];
		cin>>t>>l>>r>>c;
		if(l--==1) chk[i]|=1;
		if(r==N) chk[i]|=2;
		x.push_back(l+t);
		x.push_back(r+t);
		y.push_back(l-t);
		y.push_back(r-t);
		tie(t,l,r,aa)=make_tuple(l+t,l-t,r+t,r-t);
	}
	sort(x.begin(),x.end()); x.resize(unique(x.begin(),x.end())-x.begin());
	sort(y.begin(),y.end()); y.resize(unique(y.begin(),y.end())-y.begin());
	for(int i=0;i<M;i++) {
		auto &[x1,y1,x2,y2,c]=A[i];
		x1=lower_bound(x.begin(),x.end(),x1)-x.begin();
		y1=lower_bound(y.begin(),y.end(),y1)-y.begin();
		x2=lower_bound(x.begin(),x.end(),x2)-x.begin();
		y2=lower_bound(y.begin(),y.end(),y2)-y.begin();
		if(chk[i]&1) Q.emplace(-(dist[i]=c),i);
		else {
			set_tree(xtree,x1,x2,y1,y2,i);
			set_tree(ytree,y1,y2,x1,x2,i);
		}
	}
	while(!Q.empty()) {
		auto[t,c]=Q.top();
		Q.pop();
		P.clear();
		auto[x1,y1,x2,y2,d]=A[c];
		get_pos(xtree,x1,x2,y1,y2); get_pos(ytree,y1,y2,x1,x2);
		for(auto n: P) if(dist[n]==INF) {
			auto[x1,y1,x2,y2,d]=A[n];
			dist[n]=dist[c]+d;
			erase_tree(xtree,x1,x2,y1,y2,n);
			erase_tree(ytree,y1,y2,x1,x2,n);
			Q.emplace(-dist[n],n);
		}
	}
	ans=INF;
	for(int i=0;i<M;i++) if(chk[i]&2) ans=min(ans,dist[i]);
	cout<<(ans<INF ? ans:-1)<<'\n';
	return 0;
}

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