Submission #364438

#	Time	Username	Problem	Language	Result	Execution time	Memory
364438		arnold518	방벽 (JOI15_walls)	C++14	100 / 100	914 ms	38248 KiB

walls

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

struct Data
{
	int l, r, p;
};

int N, M;
Data A[MAXN+10];
int B[MAXN+10];
int C[MAXN+10], D[MAXN+10];
ll ans2[MAXN+10];

set<pii> S;
set<int> S2;

int getr(int x)
{
	if(x==-1) return -1;
	auto it=S2.find(x);
	assert(it!=S2.end());
	it=next(it);
	if(it==S2.end()) return -1;
	else return *it;
}

int getl(int x)
{
	if(x==-1) return -1;
	auto it=S2.find(x);
	assert(it!=S2.end());
	if(it==S2.begin()) return -1;
	it=prev(it);
	return *it;
}

struct BIT
{
	ll tree[MAXN+10];
	void update(int i, ll k)
	{
		for(i=M-i+1; i<=M; i+=(i&-i)) tree[i]+=k;
	}
	ll query(int i)
	{
		ll ret=0;
		for(i=M-i+1; i>0; i-=(i&-i)) ret+=tree[i];
		return ret;
	}
}bit1, bit2;

int main()
{
	scanf("%d%d", &N, &M);
	for(int i=1; i<=N; i++)
	{
		scanf("%d%d", &A[i].l, &A[i].r);
		A[i].p=i;
	}
	for(int i=1; i<=M; i++) scanf("%d", &B[i]);
	M=unique(B+1, B+M+1)-B-1;
	vector<int> V;
	V.push_back(B[1]);
	for(int i=2; i<M; i++)
	{
		if(B[i-1]<B[i] && B[i+1]<B[i]) V.push_back(B[i]);
		else if(B[i-1]>B[i] && B[i+1]>B[i]) V.push_back(B[i]);
	}
	V.push_back(B[M]);
 
	for(int i=0; i<V.size(); i++) B[i+1]=V[i];
	M=V.size();

	sort(A+1, A+N+1, [&](const Data &p, const Data &q)
	{
		return p.r-p.l<q.r-q.l;
	});

	for(int i=1; i<M; i++)
	{
		S.insert({abs(B[i+1]-B[i]), i});
		bit1.update(i, abs(B[i+1]-B[i]));
		bit2.update(i, 1);
	}
	for(int i=1; i<=M; i++)
	{
		S2.insert(i);
		C[i]=D[i]=B[i];
	}
	for(int i=2; i<=M; i++)
	{
		C[i]=max(C[i], C[i-1]);
		D[i]=min(D[i], D[i-1]);
	}

	//for(int i=1; i<=M; i++) printf("%d ", B[i]); printf("\n");
	for(int i=1; i<=N; i++)
	{
		int len=A[i].r-A[i].l+1;
		while(S.size()>1 && S.begin()->first<len)
		{
			int p=S.begin()->second;
			int q=getr(p);
			int r=getr(q);

			if(getl(p)==-1)
			{
				bit1.update(p, -abs(B[p]-B[q])); bit2.update(p, -1);
				S.erase({abs(B[p]-B[q]), p});
				S2.erase(p);
			}
			else if(r!=-1)
			{
				if(B[p]>B[q])
				{
					if(B[r]<=B[p])
					{
						int t=getr(r);
						bit1.update(p, -abs(B[p]-B[q])); bit2.update(p, -1);
						S.erase({abs(B[p]-B[q]), p});
						bit1.update(q, -abs(B[r]-B[q])); bit2.update(q, -1);
						S.erase({abs(B[r]-B[q]), q});
						if(t!=-1)
						{
							bit1.update(r, -abs(B[t]-B[r])); bit2.update(r, -1);
							S.erase({abs(B[t]-B[r]), r});
							bit1.update(p, abs(B[p]-B[t])); bit2.update(p, 1);
							S.insert({abs(B[p]-B[t]), p});
						}
						S2.erase(q);
						S2.erase(r);
					}
					else
					{
						int t=getl(p);
						if(t!=-1)
						{
							bit1.update(p, -abs(B[p]-B[q])); bit2.update(p, -1);
							S.erase({abs(B[p]-B[q]), p});
							bit1.update(q, -abs(B[r]-B[q])); bit2.update(q, -1);
							S.erase({abs(B[r]-B[q]), q});							
							bit1.update(t, -abs(B[t]-B[p])); bit2.update(t, -1);
							S.erase({abs(B[t]-B[p]), t});	
							bit1.update(t, abs(B[r]-B[t])); bit2.update(t, 1);
							S.insert({abs(B[r]-B[t]), t});
							S2.erase(p);
							S2.erase(q);
						}
						else
						{
							bit1.update(p, -abs(B[p]-B[q])); bit2.update(p, -1);
							S.erase({abs(B[p]-B[q]), p});
							bit1.update(q, -abs(B[r]-B[q])); bit2.update(q, -1);
							S.erase({abs(B[r]-B[q]), q});							
							bit1.update(p, abs(B[r]-B[p])); bit2.update(p, 1);
							S.insert({abs(B[r]-B[p]), p});
							S2.erase(q);
						}
					}
				}
				else
				{
					if(B[r]>=B[p])
					{
						int t=getr(r);
						bit1.update(p, -abs(B[p]-B[q])); bit2.update(p, -1);
						S.erase({abs(B[p]-B[q]), p});
						bit1.update(q, -abs(B[r]-B[q])); bit2.update(q, -1);
						S.erase({abs(B[r]-B[q]), q});
						if(t!=-1)
						{
							bit1.update(r, -abs(B[t]-B[r])); bit2.update(r, -1);
							S.erase({abs(B[t]-B[r]), r});
							bit1.update(p, abs(B[p]-B[t])); bit2.update(p, 1);
							S.insert({abs(B[p]-B[t]), p});
						}
						S2.erase(q);
						S2.erase(r);
					}
					else
					{
						int t=getl(p);
						if(t!=-1)
						{
							bit1.update(p, -abs(B[p]-B[q])); bit2.update(p, -1);
							S.erase({abs(B[p]-B[q]), p});
							bit1.update(q, -abs(B[r]-B[q])); bit2.update(q, -1);
							S.erase({abs(B[r]-B[q]), q});							
							bit1.update(t, -abs(B[t]-B[p])); bit2.update(t, -1);
							S.erase({abs(B[t]-B[p]), t});	
							bit1.update(t, abs(B[r]-B[t])); bit2.update(t, 1);
							S.insert({abs(B[r]-B[t]), t});
							S2.erase(p);
							S2.erase(q);
						}
						else
						{
							bit1.update(p, -abs(B[p]-B[q])); bit2.update(p, -1);
							S.erase({abs(B[p]-B[q]), p});
							bit1.update(q, -abs(B[r]-B[q])); bit2.update(q, -1);
							S.erase({abs(B[r]-B[q]), q});							
							bit1.update(p, abs(B[r]-B[p])); bit2.update(p, 1);
							S.insert({abs(B[r]-B[p]), p});
							S2.erase(q);
						}
					}
				}
			}
			else
			{
				bit1.update(p, -abs(B[p]-B[q])); bit2.update(p, -1);
				S.erase({abs(B[p]-B[q]), p});
				S2.erase(q);
			}
		}
		int t1=upper_bound(C+1, C+M+1, A[i].r)-C;
		int t2=lower_bound(D+1, D+M+1, A[i].l, greater<int>())-D;
		auto it=S2.lower_bound(min(t1, t2));
		ll ans=0;
		//printf("%d\n", len);
		//for(auto it : S2) printf("%d ", it); printf("\n");
		if(S.size()==1)
		{
			int l=A[i].l, r=A[i].r;
			for(auto jt : S2)
			{
				int it=B[jt];
				if(l<=it && it<=r) continue;
				else if(it<l)
				{
					int t=l-it;
					ans+=t; l-=t; r-=t;
				}
				else if(it>r)
				{
					int t=it-r;
					ans+=t; l+=t; r+=t;
				}
			}
		}
		else if(it!=S2.end())
		{
			if(it!=S2.begin())
			{
				if(B[*prev(it)]>B[*it])
				{
					ans=abs(B[*it]-A[i].l);
				}
				else
				{
					ans=abs(B[*it]-A[i].r);
				}
			}
			else if(next(it)!=S2.end())
			{
				if(B[*next(it)]>B[*it])
				{
					ans=abs(B[*it]-A[i].l);
				}
				else
				{
					ans=abs(B[*it]-A[i].r);
				}	
			}
			else assert(0);
			//printf("%d %d / %lld %lld %lld / %d\n", A[i].l, A[i].r, ans, bit1.query(*it), bit2.query(*it), *it);
			if(S.size()>1 || S.begin()->first>=len)
			{
				ans+=bit1.query(*it);
				ans-=bit2.query(*it)*(len-1);
			}
		}
		ans2[A[i].p]=ans;
	}
	for(int i=1; i<=N; i++) printf("%lld\n", ans2[i]);
}	

Compilation message (stderr)

walls.cpp: In function 'int main()':
walls.cpp:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i=0; i<V.size(); i++) B[i+1]=V[i];
      |               ~^~~~~~~~~
walls.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
walls.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |   scanf("%d%d", &A[i].l, &A[i].r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
walls.cpp:67:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |  for(int i=1; i<=M; i++) scanf("%d", &B[i]);
      |                          ~~~~~^~~~~~~~~~~~~

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