oj.uz

Submission #677516

# Submission time Handle Problem Language Result Execution time Memory
677516 2023-01-03T13:51:23 Z 79brue None (JOI15_walls) C++17
100 / 100
 1169 ms 41012 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1236 KB Output is correct
2 Correct 404 ms 20120 KB Output is correct
3 Correct 601 ms 30160 KB Output is correct
4 Correct 561 ms 30108 KB Output is correct
5 Correct 614 ms 30260 KB Output is correct
6 Correct 453 ms 30152 KB Output is correct
7 Correct 21 ms 328 KB Output is correct
8 Correct 23 ms 316 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3388 KB Output is correct
2 Correct 409 ms 21316 KB Output is correct
3 Correct 128 ms 12776 KB Output is correct
4 Correct 782 ms 40824 KB Output is correct
5 Correct 509 ms 30816 KB Output is correct
6 Correct 798 ms 41012 KB Output is correct
7 Correct 511 ms 30820 KB Output is correct
8 Correct 794 ms 40856 KB Output is correct
9 Correct 104 ms 9520 KB Output is correct
10 Correct 378 ms 40296 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1236 KB Output is correct
2 Correct 404 ms 20120 KB Output is correct
3 Correct 601 ms 30160 KB Output is correct
4 Correct 561 ms 30108 KB Output is correct
5 Correct 614 ms 30260 KB Output is correct
6 Correct 453 ms 30152 KB Output is correct
7 Correct 21 ms 328 KB Output is correct
8 Correct 23 ms 316 KB Output is correct
9 Correct 29 ms 3388 KB Output is correct
10 Correct 409 ms 21316 KB Output is correct
11 Correct 128 ms 12776 KB Output is correct
12 Correct 782 ms 40824 KB Output is correct
13 Correct 509 ms 30816 KB Output is correct
14 Correct 798 ms 41012 KB Output is correct
15 Correct 511 ms 30820 KB Output is correct
16 Correct 794 ms 40856 KB Output is correct
17 Correct 104 ms 9520 KB Output is correct
18 Correct 378 ms 40296 KB Output is correct
19 Correct 714 ms 30876 KB Output is correct
20 Correct 1148 ms 40800 KB Output is correct
21 Correct 718 ms 30888 KB Output is correct
22 Correct 972 ms 36852 KB Output is correct
23 Correct 708 ms 30924 KB Output is correct
24 Correct 1169 ms 40680 KB Output is correct
25 Correct 122 ms 9800 KB Output is correct
26 Correct 121 ms 10328 KB Output is correct
27 Correct 483 ms 40300 KB Output is correct