Submission #56971

#	Time	Username	Problem	Language	Result	Execution time	Memory
56971		babo	방벽 (JOI15_walls)	C++14	0 / 100	56 ms	4960 KiB

walls

#include <bits/stdc++.h>
#define L long long

using namespace std;

L n,m,lensum;

struct Wall{
	L s,e,len,ord,ans;
}a[200020];

bool operator<(Wall a,Wall b){
	return a.len<b.len;
}

bool cmp(Wall a,Wall b){
	return a.ord<b.ord;
}

L lazor[200020];
vector<L>lazors;

struct Line{
	L s,e,det,ord,len;
};

bool operator<(Line a,Line b){
	return a.len<b.len;
}

bool operator==(Line a,Line b){
	return a.s==b.s&&a.len==b.len&&a.e==b.e&&a.ord==b.ord;
}

struct Line2{
	L s,e,det,ord,len;
	void copy(Line temp){
		s=temp.s;
		e=temp.e;
		det=temp.det;
		ord=temp.ord;
		len=temp.len;
	}
};

bool operator<(Line2 a,Line2 b){
	return a.ord<b.ord;
}

bool operator==(Line2 a,Line2 b){
	return a.s==b.s&&a.len==b.len&&a.e==b.e&&a.ord==b.ord;
}

set<Line>st;
set<Line2>st2;

vector<Line>lines;

void do1(){
	L i;
	for(i=1;i<=n;i++)
	{
		L ansans=0;
		if(a[i].s>lazor[1]) ansans=a[i].s-lazor[1];
		else if(a[i].e<lazor[1]) ansans=lazor[1]-a[i].e;
		else ansans=0;
		printf("%lld ",ansans);
	}
	exit(0);
}

L ab(L x){
	return x>0?x:-x;
}


int main()
{
	scanf("%lld %lld",&n,&m);
	L i;
	for(i=1;i<=n;i++)
	{
		scanf("%lld %lld",&a[i].s,&a[i].e);
		a[i].len=a[i].e-a[i].s;
		a[i].ord=i;
		a[i].ans=0;
	}
	for(i=1;i<=m;i++)
	{
		scanf("%lld",&lazor[i]);
	}
	if(m==1)
	{
		do1();
		return 0;
	}
	sort(a+1,a+n+1);
	for(i=1;i<=m;i++)
	{
		if(lazors.size()&&i<m&&(lazor[i]-lazors[lazors.size()-1])*(lazor[i]-lazor[i+1])<0)
		{
			continue;
		}
		lazors.push_back(lazor[i]);
	}
	for(i=1;i<lazors.size();i++)
	{
		Line temp;
		temp.s=lazors[i-1];
		temp.e=lazors[i];
		temp.det=temp.s<temp.e;
		temp.len=temp.e-temp.s;
		if(temp.len<0) temp.len*=-1;
		lensum+=temp.len;
		temp.ord=i;
		lines.push_back(temp);
		Line2 temp2;
		temp2.copy(temp);
		st.insert(temp);
		st2.insert(temp2);
	}
	//printf("lensum %lld\n",lensum);
	for(i=1;i<=n;i++)
	{
		while(1)
		{
			set<Line>::iterator it=st.begin();
			if(it==st.end()) break;
			if(it->len<=a[i].len)
			{
				//puts("1");
				Line2 temp;
				temp.ord=it->ord;
				st.erase(it);
				set<Line2>::iterator it2=st2.lower_bound(temp);
				if(it2==st2.begin())
				{
					set<Line2>::iterator it3=it2;
					it3++;
					if(it3==st2.end()) continue;
					
					Line2 out2=*it2;
					Line out;
					out.s=out2.s;
					out.e=out2.e;
					out.ord=out2.ord;
					out.det=out2.det;
					out.len=out2.len;
					
					lensum-=out.len;
					
					st.erase(out);
					st2.erase(out2);
					continue;
				}
				else
				{
					set<Line2>::iterator it3=it2;
					it3++;
					if(it3==st2.end()) 
					{
						Line2 out2=*it2;
						Line out;
						out.s=out2.s;
						out.e=out2.e;
						out.ord=out2.ord;
						out.det=out2.det;
						out.len=out2.len;
						
						lensum-=out.len;
						
						st.erase(out);
						st2.erase(out2);
						continue;
					}
				}
					
				Line2 now2=*it2;
				it2++;
				Line2 next2=*it2;
				it2--;
				it2--;
				Line2 prev2=*it2;
				
				Line now;
				now.s=now2.s;
				now.e=now2.e;
				now.det=now2.det;
				now.len=now2.len;
				now.ord=now2.ord;
				Line next;
				next.s=next2.s;
				next.e=next2.e;
				next.det=next2.det;
				next.len=next2.len;
				next.ord=next2.ord;
				Line prev;
				prev.s=prev2.s;
				prev.e=prev2.e;
				prev.det=prev2.det;
				prev.len=prev2.len;
				prev.ord=prev2.ord;
				
				st.erase(now);
				st.erase(next);
				st.erase(prev);
				st2.erase(now2);
				st2.erase(next2);
				st2.erase(prev2);
				
				//printf("********%lld %lld\n",lensum,now.len);
				lensum-=2*now.len;
				
				if(it2->det==1)
				{
					Line input;
					input.s=prev.s;
					input.e=next.e;
					input.len=input.s-input.e;
					input.det=0;
					input.ord=now.ord;
					Line2 input2;
					input2.copy(input);
					st.insert(input);
					st2.insert(input2);
				}
				else
				{
					Line input;
					input.s=prev.s;
					input.e=next.e;
					input.len=input.e-input.s;
					input.det=1;
					input.ord=now.ord;
					Line2 input2;
					input2.copy(input);
					st.insert(input);
					st2.insert(input2);
				}
			}
			else break;
		}
		/*puts("");
		set<Line2>::iterator itit;
		for(itit=st2.begin();itit!=st2.end();itit++)
			printf("%lld %lld\n",itit->s,itit->e);
		
		puts("");
		*/
		//printf("%lld\n",lensum);
		set<Line2>::iterator it=st2.begin();
		if(it->det==1) a[i].ans=ab((it->s)-a[i].s);
		else a[i].ans=ab((it->s)-a[i].e);
		//printf("%lld %lld ",a[i].ord,a[i].ans);
		a[i].ans+=lensum-(st2.size())*a[i].len;
		//printf("%lld\n",a[i].ans);
	}
	sort(a+1,a+n+1,cmp);
	for(i=1;i<=n;i++)
	{
		printf("%lld\n",a[i].ans);
	}
}

Compilation message (stderr)

walls.cpp: In function 'int main()':
walls.cpp:106:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=1;i<lazors.size();i++)
          ~^~~~~~~~~~~~~~
walls.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~
walls.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&a[i].s,&a[i].e);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
walls.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&lazor[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 45
• Subtask 3: 0 / 45