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;
const int MN = 200010;
int N, M;
struct Query {
int l, r, id;
bool operator <(const Query &i) const {
return r - l < i.r - i.l;
}
};
Query P[MN];
int Q[MN];
vector<int> tmp;
bool bad(int a, int b, int c) {
return (a < b && b < c) || (a > b && b > c);
}
struct Info {
int d, t1, t2;
bool operator <(const Info &i) const {
return d < i.d;
}
};
set<pii> st;
set<Info> diff;
ll sum;
int cnt;
ll ans[MN];
int main() {
scanf("%d %d", &N, &M);
for(int i = 0; i < N; i++) {
scanf("%d %d", &P[i].l, &P[i].r);
P[i].id = i;
}
for(int i = 0; i < M; i++) {
scanf("%d", &Q[i]);
}
tmp.push_back(Q[0]);
for(int i = 1; i < M; i++) {
if(tmp.size() && tmp.back() == Q[i]) continue;
if(tmp.size() >= 2 && bad(tmp[ (int)tmp.size() - 2 ], tmp.back(), Q[i])) {
tmp.pop_back();
}
tmp.push_back(Q[i]);
}
M = tmp.size();
for(int i = 0; i < M; i++) Q[i] = tmp[i];
if(M >= 2 && Q[0] > Q[1]) {
for(int i = 0; i < N; i++) {
P[i].l = -P[i].l;
P[i].r = -P[i].r;
swap(P[i].l, P[i].r);
}
for(int i = 0; i < M; i++) {
Q[i] = -Q[i];
}
}
sort(P, P + N);
for(int i = 0; i < M; i++) {
st.insert({ i, Q[i] });
if(i) {
diff.insert({ abs(Q[i] - Q[i - 1]), i - 1, i });
sum += abs(Q[i] - Q[i - 1]);
cnt++;
}
}
for(int i = 0; i < N; i++) {
while(cnt > 1 && diff.begin()->d <= P[i].r - P[i].l) {
Info info = *diff.begin();
diff.erase(info);
int t1 = info.t1;
int t2 = info.t2;
sum -= info.d;
cnt--;
if(t1 == st.begin()->first) {
st.erase(pii(t1, Q[t1]));
}
else if(t2 == st.rbegin()->first) {
st.erase(pii(t2, Q[t2]));
}
else {
set<pii>::iterator it1 = st.lower_bound({ t1, Q[t1] });
set<pii>::iterator it2 = st.lower_bound({ t2, Q[t2] });
int t0 = (--it1)->first;
int t3 = (++it2)->first;
diff.erase({ abs(Q[t0] - Q[t1]), t0, t1 });
diff.erase({ abs(Q[t2] - Q[t3]), t2, t3 });
sum -= abs(Q[t0] - Q[t1]);
sum -= abs(Q[t2] - Q[t3]);
st.erase(pii(t1, Q[t1]));
st.erase(pii(t2, Q[t2]));
diff.insert({ abs(Q[t0] - Q[t3]), t0, t3 });
sum += abs(Q[t0] - Q[t3]);
cnt--;
}
}
/*
for(set<pii>::iterator it = st.begin(); it != st.end(); it++) {
cout << it->second << ' ';
}
cout << endl;
//*/
if(cnt <= 1) {
for(set<pii>::iterator it = st.begin(); it != st.end(); it++) {
if(P[i].l <= it->second && it->second <= P[i].r) continue;
else if(P[i].r < it->second) {
int d = it->second - P[i].r;
P[i].l += d;
P[i].r += d;
ans[ P[i].id ] += d;
}
else {
int d = P[i].l - it->second;
P[i].l -= d;
P[i].r -= d;
ans[ P[i].id ] += d;
}
}
}
else {
int add = st.begin()->first % 2? abs(P[i].r - st.begin()->second) : abs(P[i].l - st.begin()->second);
ans[ P[i].id ] = sum - 1LL * cnt * (P[i].r - P[i].l) + add;
}
}
for(int i = 0; i < N; i++) {
printf("%lld\n", ans[i]);
}
}
Compilation message (stderr)
walls.cpp: In function 'int main()':
walls.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~~
walls.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &P[i].l, &P[i].r);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
walls.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q[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... |