Submission #446114

#	Time	Username	Problem	Language	Result	Execution time	Memory
446114		kig9981	Treatment Project (JOI20_treatment)	C++17	9 / 100	560 ms	55484 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;
vector<pair<int,int>> tree[2*SZ];
vector<pair<int,long long>> U[200000], qry[200000];
vector<int> P, x, y;
vector<tuple<int,int,int,int,int>> A;
long long dist1[100000], dist2[100000], mtree[200001];
int chk[100000];

void set_tree(int s, int e, int p, int i)
{
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) tree[s++].emplace_back(p,i);
		if(~e&1) tree[e--].emplace_back(p,i);
	}
}

void get_pos(int n, int l)
{
	for(n+=SZ;n;n>>=1) while(tree[n].size() && l<=tree[n].back().first) {
		P.push_back(tree[n].back().second);
		tree[n].pop_back();
	}
}

void update(int n, long long v) {for(++n;n<=200000;n+=n&-n) mtree[n]=min(mtree[n],v);}

long long get_min(int n)
{
	long long ret=INF;
	for(++n;n;n-=n&-n) ret=min(ret,mtree[n]);
	return ret;
}

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=INF;
	cin>>N>>M; A.resize(M);
	memset(dist1,0x3f,sizeof(dist1));
	memset(dist2,0x3f,sizeof(dist2));
	for(int i=0;i<M;i++) {
		auto &[t,l,r,aa,c]=A[i];
		cin>>t>>l>>r>>c;
		if(--l==0) 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(-(dist1[i]=c),i);
		else set_tree(x1,x2,-y1,i);
	}
	for(int i=2*SZ;--i;) sort(tree[i].begin(),tree[i].end());
	while(!Q.empty()) {
		auto[t,c]=Q.top();
		Q.pop();
		P.clear();
		auto[x1,y1,x2,y2,d]=A[c];
		get_pos(x2,-y2);
		for(auto n: P) if(dist1[n]==INF) {
			auto[x1,y1,x2,y2,d]=A[n];
			dist1[n]=dist1[c]+d;
			Q.emplace(-dist1[n],n);
		}
	}
	for(int i=2*SZ;--i;) tree[i].clear();
	for(int i=0;i<M;i++) {
		auto[x1,y1,x2,y2,c]=A[i];
		if(chk[i]&2) Q.emplace(-(dist2[i]=c),i);
		else set_tree(y1,y2,x2,i);
	}
	for(int i=2*SZ;--i;) sort(tree[i].begin(),tree[i].end());
	while(!Q.empty()) {
		auto[t,c]=Q.top();
		Q.pop();
		P.clear();
		auto[x1,y1,x2,y2,d]=A[c];
		get_pos(y1,x1);
		for(auto n: P) if(dist2[n]==INF) {
			auto[x1,y1,x2,y2,d]=A[n];
			dist2[n]=dist2[c]+d;
			Q.emplace(-dist2[n],n);
		}
	}
	for(int i=0;i<M;i++) {
		auto[x1,y1,x2,y2,c]=A[i];
		ans=min(ans,dist1[i]+dist2[i]-c);
		U[x1].emplace_back(y1,dist2[i]);
		qry[x2].emplace_back(y2,dist1[i]);
	}
	memset(mtree,0x3f,sizeof(mtree));
	for(int i=0;i<x.size();i++) {
		for(auto[p,v]: U[i]) update(p,v);
		for(auto[p,v]: qry[i]) ans=min(ans,get_min(p)+v);
	}
	cout<<(ans<INF ? ans:-1)<<'\n';
	return 0;
}

Compilation message (stderr)

treatment.cpp: In function 'int main()':
treatment.cpp:121:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |  for(int i=0;i<x.size();i++) {
      |              ~^~~~~~~~~

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