Submission #57794

#	Time	Username	Problem	Language	Result	Execution time	Memory
57794		choikiwon	방벽 (JOI15_walls)	C++17	100 / 100	1201 ms	125168 KiB

walls

#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 {
        if(d != i.d) return d < i.d;
        if(t1 != i.t1) return t1 < i.t1;
        if(t2 != i.t2) return t2 < i.t2;
        return false;
    }
};

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:41: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:44: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:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &Q[i]);
         ~~~~~^~~~~~~~~~~~~

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