oj.uz

Submission #677473

# Submission time Handle Problem Language Result Execution time Memory
677473 2023-01-03T12:08:59 Z jhwest2 None (JOI15_walls) C++17
100 / 100
 563 ms 29916 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 202020;
const int INF = 1e9 + 10;

int n, m, a[N], b[N], ord[N], dir[N], pmin[N], pmax[N]; ll ans[N];
vector<int> q;
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    for (int i = 1; i <= m; i++) {
        int x; cin >> x;
        if (!q.empty() && q.back() == x)
            continue;
        if (q.size() >= 2 && (q[q.size() - 2] < q.back()) == (q.back() < x))
            q.pop_back();
        q.push_back(x);
    }

    // determine direction 
    pmin[0] = pmax[0] = q[0];
    for (int i = 1; i < q.size(); i++) {
        pmin[i] = min(pmin[i - 1], q[i]);
        pmax[i] = max(pmax[i - 1], q[i]);
    }
    for (int i = 1; i <= n; i++) {
        int L = 0, R = (int)q.size();
        while (L < R) {
            int M = (L + R) / 2;
            if (pmin[M] < a[i] || pmax[M] > b[i])
                R = M;
            else
                L = M + 1;
        }
        if (R != q.size()) {
            if (pmin[L] < a[i])
                dir[i] = 1; // go left
            else
                dir[i] = 2; // go right
        }
    }
    if (q.size() == 1) {
        for (int i = 1; i <= n; i++) {
            if (dir[i] == 0)
                cout << 0 << '\n';
            if (dir[i] == 1)
                cout << a[i] - q[0] << '\n';
            if (dir[i] == 2)
                cout << q[0] - b[i] << '\n';
        }
        return 0;
    }
    
    for (int i = 1; i <= n; i++) {
        if (dir[i] == 1)
            a[i] += INF, b[i] += INF, ans[i] -= INF;
        if (dir[i] == 2)
            a[i] -= INF, b[i] -= INF, ans[i] -= INF;
    }

    for (int i = 1; i <= n; i++) 
        ord[i] = i;
    sort(ord + 1, ord + 1 + n, [&](auto i, auto j) {
        return b[i] - a[i] < b[j] - a[j];
    });

    set<pair<int, int>> st;
    set<pair<int, int>> pq;
    for (int i = 0; i < q.size(); i++) {
        st.insert({i, q[i]});
        if (i != 0)
            pq.insert({abs(q[i] - q[i - 1]), i - 1});
    }

    ll len = 0, cnt = (int)q.size() - 1;
    for (int i = 1; i < q.size(); i++)
        len += abs(q[i] - q[i - 1]);

    for (int i = 1; i <= n; i++) {
        if (dir[ord[i]] == 0)
            continue;

        int l = a[ord[i]], r = b[ord[i]];
        while (pq.size() >= 2 && pq.begin()->first <= r - l) {
            auto [x, y] = *pq.begin(); pq.erase(pq.begin());
            --cnt;

            auto it = st.lower_bound({y, q[y]});
            if (it == st.begin()) {
                st.erase(it);
                len -= x;
            }
            else if (next(next(it)) == st.end()) {
                st.erase(next(it));
                len -= x;
            }
            else {
                pq.erase({abs(it->second - prev(it)->second), prev(it)->first});
                it = st.erase(it);
                pq.erase({abs(it->second - next(it)->second), it->first});
                it = st.erase(it);
                pq.insert({abs(it->second - prev(it)->second), prev(it)->first});
                --cnt;
                len -= 2 * x;
            }
        } 
        int s = st.begin()->second;
        int t = next(st.begin())->second;

        if (cnt == 1) {
            if (s < t) {
                if (dir[ord[i]] == 1)
                    ans[ord[i]] += (ll)l - s + max(0, t - s - r + l);
                else
                    ans[ord[i]] += (ll)t - r;
            }
            else {
                if (dir[ord[i]] == 1)
                    ans[ord[i]] += (ll)l - t;
                else
                    ans[ord[i]] += (ll)s - r + max(0, s - t - r + l);
            }
        }
        else {
            ans[ord[i]] += len - cnt * (r - l);

            if (s < t) 
                ans[ord[i]] += abs(l - s);
            else 
                ans[ord[i]] += abs(r - s);
        }

        // cout << i << "!\n";
        // for (auto [x, y] : st)
        //     cout << y << ' ';
        // cout << '\n';
        // cout << len << ' ' << cnt << ' ' << "?\n";

        // cout << l << ' ' << r << ' ' << s << ' '<< t << "!!!\n";

    }
    for (int i = 1; i <= n; i++)
        cout << ans[i] << '\n';
}

Compilation message

walls.cpp: In function 'int main()':
walls.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i = 1; i < q.size(); i++) {
      |                     ~~^~~~~~~~~~
walls.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         if (R != q.size()) {
      |             ~~^~~~~~~~~~~
walls.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 0; i < q.size(); i++) {
      |                     ~~^~~~~~~~~~
walls.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i = 1; i < q.size(); i++)
      |                     ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 205 ms 14436 KB Output is correct
3 Correct 332 ms 21376 KB Output is correct
4 Correct 321 ms 21468 KB Output is correct
5 Correct 316 ms 21468 KB Output is correct
6 Correct 249 ms 21436 KB Output is correct
7 Correct 16 ms 340 KB Output is correct
8 Correct 17 ms 344 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2516 KB Output is correct
2 Correct 271 ms 15200 KB Output is correct
3 Correct 95 ms 9088 KB Output is correct
4 Correct 531 ms 29224 KB Output is correct
5 Correct 333 ms 21980 KB Output is correct
6 Correct 512 ms 29172 KB Output is correct
7 Correct 360 ms 21976 KB Output is correct
8 Correct 563 ms 29132 KB Output is correct
9 Correct 59 ms 3968 KB Output is correct
10 Correct 224 ms 28652 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 205 ms 14436 KB Output is correct
3 Correct 332 ms 21376 KB Output is correct
4 Correct 321 ms 21468 KB Output is correct
5 Correct 316 ms 21468 KB Output is correct
6 Correct 249 ms 21436 KB Output is correct
7 Correct 16 ms 340 KB Output is correct
8 Correct 17 ms 344 KB Output is correct
9 Correct 20 ms 2516 KB Output is correct
10 Correct 271 ms 15200 KB Output is correct
11 Correct 95 ms 9088 KB Output is correct
12 Correct 531 ms 29224 KB Output is correct
13 Correct 333 ms 21980 KB Output is correct
14 Correct 512 ms 29172 KB Output is correct
15 Correct 360 ms 21976 KB Output is correct
16 Correct 563 ms 29132 KB Output is correct
17 Correct 59 ms 3968 KB Output is correct
18 Correct 224 ms 28652 KB Output is correct
19 Correct 338 ms 22804 KB Output is correct
20 Correct 501 ms 29916 KB Output is correct
21 Correct 362 ms 22820 KB Output is correct
22 Correct 453 ms 27032 KB Output is correct
23 Correct 330 ms 22748 KB Output is correct
24 Correct 521 ms 29904 KB Output is correct
25 Correct 78 ms 4904 KB Output is correct
26 Correct 102 ms 7852 KB Output is correct
27 Correct 247 ms 29376 KB Output is correct