#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct dat{
int a, b, idx;
dat(){}
dat(int a, int b, int idx): a(a), b(b), idx(idx){}
bool operator<(const dat &r)const{
return b-a<r.b-r.a;
}
};
int n, k;
ll a[200002], b[200002];
ll pnt[200002];
ll minPnt[200002], maxPnt[200002];
ll ans[200002];
int searchDir[200002];
vector<dat> queries;
void input();
void solve();
void output();
int main(){
input();
solve();
output();
}
void input(){
scanf("%d %d", &n, &k);
for(int i=1; i<=n; i++) scanf("%lld %lld", &a[i], &b[i]);
for(int i=1; i<=k; i++){
scanf("%lld", &pnt[i]);
if(i>=2 && pnt[i] == pnt[i-1]) i--, k--;
else if(i>=3 && ((pnt[i-2]<=pnt[i-1]&&pnt[i-1]<=pnt[i]) || (pnt[i-2]>=pnt[i-1]&&pnt[i-1]>=pnt[i])))
pnt[i-1] = pnt[i], i--, k--;
}
}
void init(){
queries.clear();
for(int i=1; i<=n; i++) queries.push_back(dat(a[i], b[i], i));
sort(queries.begin(), queries.end());
minPnt[0] = 1e9, maxPnt[0] = 0;
for(int i=1; i<=k; i++){
minPnt[i] = min(minPnt[i-1], pnt[i]);
maxPnt[i] = max(maxPnt[i-1], pnt[i]);
}
for(int i=1; i<=n; i++){
int l = 1, r = k, ans = k+1;
while(l <= r){
int m = (l+r)/2;
if(minPnt[m] < a[i] || maxPnt[m] > b[i]) ans = m, r = m-1;
else l = m+1;
}
if(ans == k+1) continue;
if(pnt[ans] < a[i]) searchDir[i] = 2;
else searchDir[i] = 1;
}
}
struct Point{
int idx, x, dir;
Point(){}
Point(int idx, int x, int dir): idx(idx), x(x), dir(dir){}
bool operator<(const Point &r)const{
return idx<r.idx;
}
};
struct Diff{
int lidx, ridx, diff;
Diff(){}
Diff(int lidx, int ridx, int diff): lidx(lidx), ridx(ridx), diff(diff){}
bool operator<(const Diff &r)const{
if(diff != r.diff) return diff < r.diff;
return lidx > r.lidx;
}
};
ll diffSum;
multiset<Point> points;
multiset<Diff> diffs;
void insertDiff(Point it1, Point it2){
Diff d = Diff(it1.idx, it2.idx, abs(it1.x - it2.x));
diffSum += d.diff;
diffs.insert(d);
}
void eraseDiff(Point it1, Point it2){
Diff d = Diff(it1.idx, it2.idx, abs(it1.x - it2.x));
diffSum -= d.diff;
diffs.erase(diffs.find(d));
}
void solve(int mark){
/// searchDir이 1인 것, 즉 오른쪽으로 가야 하는 것만 체크할 예정
points.clear();
diffs.clear();
diffSum = 0;
points.insert(Point(0, 0, 0));
for(int i=1; i<=k; i++){
if(i==1 && i<k && pnt[i]<=pnt[i+1]) continue;
points.insert(Point(i, pnt[i], (pnt[i-1] < pnt[i]) ? 1 : 0));
assert((int)points.size() >= 2);
insertDiff(*prev(prev(points.end())), *prev(points.end()));
}
for(dat p: queries){
if(searchDir[p.idx] != 1) continue;
ll len = p.b - p.a;
while(!diffs.empty()){
Diff diff = *diffs.begin();
if(diff.diff > len) break;
diffs.erase(diffs.begin());
diffSum -= diff.diff;
/// 보완 작업
auto it = points.lower_bound(Point(diff.ridx, 0, 0));
if(it == points.end() || it->idx != diff.ridx) exit(1);
if(next(it) == points.end()){ /// 마지막인 경우
points.erase(it);
continue;
}
/// it는 중간. prvit와 nxtit를 만들자.
assert(next(it) != points.end() && it != points.begin());
Point pl = *prev(it), pm = *it, pr = *next(it);
if(prev(it) == points.begin()) exit(1);
Point pl2 = *prev(prev(it)); /// 항상 존재함
/// pl2와 pr을 직접 이어야 한다.
eraseDiff(pl2, pl);
eraseDiff(pm, pr);
insertDiff(pl2, pr);
points.erase(pl);
points.erase(pm);
}
ans[p.idx] = diffSum - (p.b - p.a) * (ll)diffs.size();
}
}
void solve(){
init();
solve(1); /// 오른쪽으로 가야 하는 것들
for(int i=1; i<=n; i++){
a[i] = 1e9 - a[i];
b[i] = 1e9 - b[i];
swap(a[i], b[i]);
}
for(int i=1; i<=k; i++) pnt[i] = 1e9 - pnt[i];
init();
solve(1);
}
void output(){
for(int i=1; i<=n; i++) printf("%lld\n", ans[i]);
}
Compilation message
walls.cpp: In function 'void input()':
walls.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
walls.cpp:37:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | for(int i=1; i<=n; i++) scanf("%lld %lld", &a[i], &b[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
walls.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | scanf("%lld", &pnt[i]);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
1236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
29 ms |
3356 KB |
Output is correct |
| 2 |
Correct |
417 ms |
21204 KB |
Output is correct |
| 3 |
Correct |
138 ms |
12780 KB |
Output is correct |
| 4 |
Correct |
793 ms |
40812 KB |
Output is correct |
| 5 |
Correct |
513 ms |
30900 KB |
Output is correct |
| 6 |
Correct |
825 ms |
40816 KB |
Output is correct |
| 7 |
Correct |
502 ms |
30896 KB |
Output is correct |
| 8 |
Correct |
761 ms |
40804 KB |
Output is correct |
| 9 |
Correct |
93 ms |
9492 KB |
Output is correct |
| 10 |
Correct |
372 ms |
40252 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
1236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
