Submission #445882

#	Time	Username	Problem	Language	Result	Execution time	Memory
445882		kig9981	Treatment Project (JOI20_treatment)	C++17	0 / 100	3092 ms	357456 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;

struct Seg
{
	int l, r;
	long long v;
	Seg() : l(0), r(0), v(0x3f3f3f3f3f3f3f3fLL) {}
} tree[22222222];

const long long INF=0x3f3f3f3f3f3f3f3fLL;
const int SZ=1<<18;
vector<int> P;
vector<pair<int,int>> x, y;
vector<tuple<int,int,int,int,int>> A;
long long dist[100000];
int node_cnt=2*SZ, chk[100000], lx[200000], rx[200000], ly[200000], ry[200000];

void set_tree2(int n, long long v, int p, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(s==e) {
		tree[p].v=v;
		return;
	}
	if(n<=m) {
		if(tree[p].l==0) tree[p].l=node_cnt++;
		set_tree2(n,v,tree[p].l,s,m);
	}
	else {
		if(tree[p].r==0) tree[p].r=node_cnt++;
		set_tree2(n,v,tree[p].r,m+1,e);
	}
	tree[p].v=min(tree[tree[p].l].v,tree[tree[p].r].v);
}

void set_tree(int x, int y, long long v)
{
	for(set_tree2(y,v,x+=SZ);x>>=1;) set_tree2(y,v,x);
}

long long get_min2(int n1, int n2, int p, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(n2<n1 || n2<s || e<n1 || p==0) return INF;
	if(n1<=s && e<=n2) return tree[p].v;
	return min(get_min2(n1,n2,tree[p].l,s,m),get_min2(n1,n2,tree[p].r,m+1,e));
}

long long get_min(int x1, int y1, int x2, int y2)
{
	long long ret=INF;
	for(x1+=SZ,x2+=SZ;x1<=x2;x1>>=1,x2>>=1) {
		if(x1&1) ret=min(ret,get_min2(y1,y2,x1++));
		if(~x2&1) ret=min(ret,get_min2(y1,y2,x2--));
	}
	return ret;
}

void get_pos2(int n1, int n2, long long v, int p, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(n2<n1 || n2<s || e<n1 || tree[p].v!=v) return;
	if(s==e) {
		P.push_back(y[m].second);
		return;
	}
	get_pos2(n1,n2,v,tree[p].l,s,m);
	get_pos2(n1,n2,v,tree[p].r,m+1,e);
}

void get_pos(int x1, int y1, int x2, int y2, long long v)
{
	P.clear();
	for(x1+=SZ,x2+=SZ;x1<=x2;x1>>=1,x2>>=1) {
		if(x1&1) get_pos2(y1,y2,v,x1++);
		if(~x2&1) get_pos2(y1,y2,v,x2--);
	}
}

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;
		else if(r==N) chk[i]=2;
		x.emplace_back(l+t,i);
		x.emplace_back(r+t,i);
		y.emplace_back(l-t,i);
		y.emplace_back(r-t,i);
		t=l=r=aa=-1;
	}
	sort(x.begin(),x.end()); sort(y.begin(),y.end());
	for(int i=0;i<2*M;i++) {
		if(get<0>(A[x[i].second])==-1) get<0>(A[x[i].second])=i;
		else get<2>(A[x[i].second])=i;
		if(get<1>(A[y[i].second])==-1) get<1>(A[y[i].second])=i;
		else get<3>(A[y[i].second])=i;
		lx[i]=i && x[i-1].first==x[i].first ? lx[i-1]:i;
		ly[i]=i && y[i-1].first==y[i].first ? ly[i-1]:i;
	}
	rx[2*M-1]=ry[2*M-1]=2*M-1;
	for(int i=2*M-1;--i>=0;) {
		rx[i]=x[i].first==x[i+1].first ? rx[i+1]:i;
		ry[i]=y[i].first==y[i+1].first ? ry[i+1]:i;
	}
	for(int i=0;i<M;i++) if(chk[i]!=1) {
		auto[x1,y1,x2,y2,c]=A[i];
		set_tree(x1,y1,c);
		set_tree(x2,y1,c);
		set_tree(x1,y2,c);
		set_tree(x2,y2,c);
	}
	for(int i=0;i<M;i++) if(chk[i]==1) {
		auto[x1,y1,x2,y2,c]=A[i];
		dist[i]=c; ans=get_min(lx[x1],ly[y1],rx[x2],ry[y2]);
		if(ans<INF) Q.emplace(-dist[i]-ans,i);
	}
	while(!Q.empty()) {
		auto[t,c]=Q.top();
		Q.pop();
		auto[x1,y1,x2,y2,d]=A[c];
		ans=get_min(lx[x1],ly[y1],rx[x2],ry[y2]);
		if(-t!=dist[c]+ans) {
			if(ans<INF) Q.emplace(-dist[c]-ans,c);
			continue;
		}
		get_pos(lx[x1],ly[y1],rx[x2],ry[y2],ans);
		for(auto n: P) {
			auto[x1,y1,x2,y2,nc]=A[n];
			dist[n]=dist[c]+nc;
			set_tree(x1,y1,INF);
			set_tree(x2,y1,INF);
			set_tree(x1,y2,INF);
			set_tree(x2,y2,INF);
		}
		for(auto n: P) {
			auto[x1,y1,x2,y2,nc]=A[n];
			ans=get_min(lx[x1],ly[y1],rx[x2],ry[y2]);
			if(ans<INF) Q.emplace(-dist[n]-ans,n);
		}
		ans=get_min(lx[x1],ly[y1],rx[x2],ry[y2]);
		if(ans<INF) Q.emplace(-dist[c]-ans,c);
	}
	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