답안 #57794 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57794	2018-07-16T06:55:22 Z	choikiwon	방벽 (JOI15_walls)	C++17	100 / 100	1201 ms	125168 KB

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

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

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	1144 KB	Output is correct
2	Correct	519 ms	16352 KB	Output is correct
3	Correct	639 ms	25872 KB	Output is correct
4	Correct	758 ms	27800 KB	Output is correct
5	Correct	805 ms	29824 KB	Output is correct
6	Correct	477 ms	31720 KB	Output is correct
7	Correct	32 ms	31720 KB	Output is correct
8	Correct	55 ms	31720 KB	Output is correct

Subtask #2
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	31720 KB	Output is correct
2	Correct	653 ms	31720 KB	Output is correct
3	Correct	232 ms	31720 KB	Output is correct
4	Correct	1040 ms	49020 KB	Output is correct
5	Correct	619 ms	49020 KB	Output is correct
6	Correct	1201 ms	57528 KB	Output is correct
7	Correct	642 ms	57528 KB	Output is correct
8	Correct	1086 ms	65904 KB	Output is correct
9	Correct	146 ms	65904 KB	Output is correct
10	Correct	382 ms	73140 KB	Output is correct

Subtask #3
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	1144 KB	Output is correct
2	Correct	519 ms	16352 KB	Output is correct
3	Correct	639 ms	25872 KB	Output is correct
4	Correct	758 ms	27800 KB	Output is correct
5	Correct	805 ms	29824 KB	Output is correct
6	Correct	477 ms	31720 KB	Output is correct
7	Correct	32 ms	31720 KB	Output is correct
8	Correct	55 ms	31720 KB	Output is correct
9	Correct	40 ms	31720 KB	Output is correct
10	Correct	653 ms	31720 KB	Output is correct
11	Correct	232 ms	31720 KB	Output is correct
12	Correct	1040 ms	49020 KB	Output is correct
13	Correct	619 ms	49020 KB	Output is correct
14	Correct	1201 ms	57528 KB	Output is correct
15	Correct	642 ms	57528 KB	Output is correct
16	Correct	1086 ms	65904 KB	Output is correct
17	Correct	146 ms	65904 KB	Output is correct
18	Correct	382 ms	73140 KB	Output is correct
19	Correct	718 ms	73140 KB	Output is correct
20	Correct	1196 ms	85400 KB	Output is correct
21	Correct	848 ms	85400 KB	Output is correct
22	Correct	969 ms	93708 KB	Output is correct
23	Correct	857 ms	94804 KB	Output is correct
24	Correct	1046 ms	108316 KB	Output is correct
25	Correct	187 ms	108316 KB	Output is correct
26	Correct	176 ms	108316 KB	Output is correct
27	Correct	451 ms	125168 KB	Output is correct

답안 #57794

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 45.0 / 45.0

Subtask #3 45.0 / 45.0

Subtask #1
10.0 / 10.0

Subtask #2
45.0 / 45.0

Subtask #3
45.0 / 45.0