This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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], col[MAXN+10];
ll ans[MAXN+10];
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; });
multiset<pii> S;
set<int> S2;
ll sum=0;
for(int i=1; i<M; i++) S.insert({abs(B[i+1]-B[i]), i+1}), sum+=abs(B[i+1]-B[i]);
for(int i=1; i<=M; i++) S2.insert(i), col[i]=(i+1)%2;
for(int i=1; i<=N; i++)
{
int len=A[i].r-A[i].l;
set<int> S3;
for(auto it : S)
{
if(it.first<=len) S3.insert(it.second);
else break;
}
while(!S3.empty())
{
int now=*S3.begin(), l, r;
auto it=S2.find(now);
if(col[now]==1) l=B[*prev(it)], r=B[*prev(it)]+len;
else r=B[*prev(it)], l=B[*prev(it)]-len;
vector<pii> V;
for(; it!=S2.end(); it++)
{
V.push_back({abs(B[*it]-B[*prev(it)]), *it});
if(!(l<=B[*it] && B[*it]<=r)) break;
}
if(it==S2.end())
{
for(auto jt : V)
{
if(S2.find(jt.second)!=S2.end()) S2.erase(jt.second);
if(S3.find(jt.second)!=S3.end()) S3.erase(jt.second);
if(S.find(jt)!=S.end()) S.erase(jt), sum-=jt.first;
}
}
else if(col[*it]==col[now])
{
for(auto jt : V)
{
if(S2.find(jt.second)!=S2.end()) S2.erase(jt.second);
if(S3.find(jt.second)!=S3.end()) S3.erase(jt.second);
if(S.find(jt)!=S.end()) S.erase(jt), sum-=jt.first;
}
S2.insert(*it);
auto pt=S2.find(*it), qt=prev(pt);
S.insert({abs(B[*pt]-B[*qt]), *pt}); sum+=abs(B[*pt]-B[*qt]);
}
else
{
auto kt=prev(S2.find(now));
V.push_back({abs(B[*kt]-B[*prev(kt)]), *kt});
for(auto jt : V)
{
//printf("V %d %d\n", jt.first, jt.second);
if(S2.find(jt.second)!=S2.end()) S2.erase(jt.second);
if(S3.find(jt.second)!=S3.end()) S3.erase(jt.second);
if(S.find(jt)!=S.end()) S.erase(jt), sum-=jt.first;
}
S2.insert(*it);
auto pt=S2.find(*it), qt=prev(pt);
S.insert({abs(B[*pt]-B[*qt]), *pt}); sum+=abs(B[*pt]-B[*qt]);
}
S3.erase(now);
}
//for(auto it : S) printf("%d %d\n", it.first, it.second);
//printf("=> %lld %d\n", sum, A[i].p);
bool flag=false;
int l=A[i].l, r=A[i].r;
for(auto it=S2.begin(); it!=S2.end(); it++)
{
if(B[*it]<l)
{
ans[A[i].p]+=l-B[*it];
r-=l-B[*it]; l-=l-B[*it];
}
else if(r<B[*it])
{
ans[A[i].p]+=B[*it]-r;
l+=B[*it]-r; r+=B[*it]-r;
}
//printf("!%d %lld\n", B[*it], ans[A[i].p]);
}
//printf("\n");
//ans[A[i].p]=sum-(ll)S.size()*len;
}
for(int i=1; i<=N; i++) printf("%lld\n", ans[i]);
}
Compilation message (stderr)
walls.cpp: In function 'int main()':
walls.cpp:40:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int i=0; i<V.size(); i++) B[i+1]=V[i];
| ~^~~~~~~~~
walls.cpp:116:8: warning: unused variable 'flag' [-Wunused-variable]
116 | bool flag=false;
| ^~~~
walls.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
22 | scanf("%d%d", &N, &M);
| ~~~~~^~~~~~~~~~~~~~~~
walls.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
25 | scanf("%d%d", &A[i].l, &A[i].r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
walls.cpp:28:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
28 | for(int i=1; i<=M; i++) scanf("%d", &B[i]);
| ~~~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |