oj.uz

Submission #57794

# Submission time Handle Problem Language Result Execution time Memory
57794 2018-07-16T06:55:22 Z choikiwon None (JOI15_walls) C++17
100 / 100
 1201 ms 125168 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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