oj.uz

Submission #364438

# Submission time Handle Problem Language Result Execution time Memory
364438 2021-02-09T07:24:47 Z arnold518 None (JOI15_walls) C++14
100 / 100
 914 ms 38248 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1260 KB Output is correct
2 Correct 314 ms 17248 KB Output is correct
3 Correct 502 ms 25440 KB Output is correct
4 Correct 455 ms 25568 KB Output is correct
5 Correct 497 ms 25440 KB Output is correct
6 Correct 296 ms 25440 KB Output is correct
7 Correct 26 ms 1132 KB Output is correct
8 Correct 28 ms 3052 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2668 KB Output is correct
2 Correct 457 ms 18016 KB Output is correct
3 Correct 136 ms 8684 KB Output is correct
4 Correct 847 ms 32372 KB Output is correct
5 Correct 573 ms 24288 KB Output is correct
6 Correct 863 ms 32284 KB Output is correct
7 Correct 583 ms 24288 KB Output is correct
8 Correct 898 ms 32224 KB Output is correct
9 Correct 112 ms 6380 KB Output is correct
10 Correct 367 ms 31840 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1260 KB Output is correct
2 Correct 314 ms 17248 KB Output is correct
3 Correct 502 ms 25440 KB Output is correct
4 Correct 455 ms 25568 KB Output is correct
5 Correct 497 ms 25440 KB Output is correct
6 Correct 296 ms 25440 KB Output is correct
7 Correct 26 ms 1132 KB Output is correct
8 Correct 28 ms 3052 KB Output is correct
9 Correct 32 ms 2668 KB Output is correct
10 Correct 457 ms 18016 KB Output is correct
11 Correct 136 ms 8684 KB Output is correct
12 Correct 847 ms 32372 KB Output is correct
13 Correct 573 ms 24288 KB Output is correct
14 Correct 863 ms 32284 KB Output is correct
15 Correct 583 ms 24288 KB Output is correct
16 Correct 898 ms 32224 KB Output is correct
17 Correct 112 ms 6380 KB Output is correct
18 Correct 367 ms 31840 KB Output is correct
19 Correct 592 ms 30132 KB Output is correct
20 Correct 914 ms 38248 KB Output is correct
21 Correct 581 ms 30476 KB Output is correct
22 Correct 759 ms 34784 KB Output is correct
23 Correct 604 ms 29920 KB Output is correct
24 Correct 899 ms 38176 KB Output is correct
25 Correct 131 ms 12396 KB Output is correct
26 Correct 165 ms 13164 KB Output is correct
27 Correct 377 ms 37656 KB Output is correct