Submission #677516

#	Time	Username	Problem	Language	Result	Execution time	Memory
677516		79brue	방벽 (JOI15_walls)	C++17	100 / 100	1169 ms	41012 KiB

walls

#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);
        }

        /// 실제로는 a_i = 0이 아닐 수 있기 때문에 이 부분을 수정해 줘야 한다.
        if((int)points.size() == 1){
            ans[p.idx] = max(0LL, p.a - minPnt[k]);
            continue;
        }

        int start = next(points.begin())->x;

        if(p.b <= start){ /// 밖에 있는 경우 -> 쉽다.
            ans[p.idx] = diffSum - (p.b - p.a) * (ll)diffs.size() - p.a;
        }
        else{ /// 포함된 경우
            ans[p.idx] = diffSum - (p.b - p.a) * (ll)diffs.size() - (start - len) + (p.b - start);
        }
    }
}

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 (stderr)

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]);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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