Submission #677380

#	Time	Username	Problem	Language	Result	Execution time	Memory
677380		jhwest2	방벽 (JOI15_walls)	C++17	10 / 100	22 ms	596 KiB

walls

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 202020;

int n, m, a[N], b[N]; ll c[N];
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];

    // subtask 1
    if (n == 1) {
        int l = a[1], r = b[1];

        ll ans = 0;
        while (m--) {
            int t; cin >> t;
            if (r < t) {
                int d = t - r;
                l += d;
                r += d;
                ans += d;
            }
            else if (t < l) {
                int d = l - t;
                l -= d;
                r -= d;
                ans += d;
            }
        }
        cout << ans;
    }
    else {
        while (n--)
            cout << 0 << '\n';
    }
    // subtask 2

    // bool f = true;
    // for (int i = 1; i <= n; i++) {
    //     if (a[i] != 0)
    //         f = false;
    // }
    // if (f) {
    //     sort(b + 1, b + 1 + n);
    //     for (int i = 1; i <= n; i++) 
    //         c[i] = c[i - 1] + b[i];
        
    //     ll ans = 0;
    //     set<array<int, 3>> st;
    //     st.insert({n, 2, 0});
    //     while (m--) {
    //         int t; cin >> t;

    //         int L = 1, R = n;
    //         while (L < R) {
    //             int M = (L + R + 1) / 2;

    //             auto it = st.lower_bound({M, 0, 0});
    //             int l, r;

    //             auto [x, y, z] = *it;
    //             if (y == 1)
    //                 l = z - a[x], r = z;
    //             else
    //                 l = z, r = z + a[x];

    //             if (l <= t && t <= r)
    //                 R = M - 1;
    //             else
    //                 L = M;
    //         }

    //         int p = 0;
    //         while (!st.empty()) {
    //             auto [x, y, z] = *st.begin(); 

    //             bool f = false;
    //             if (L < x) 
    //                 f = true, x = L;
    //             else
    //                 st.erase(st.begin());

    //             int l, r;

    //             if (y == 1) 
    //                 l = z - a[x], r = z;
    //             else
    //                 l = z, r = z + a[x];

    //             if (r < t) {
    //                 if (y == 1)
    //                     ans += 1ll * (x - p) * (t - r);
    //                 else
    //                     ans += 1ll * (x - p) * (t - l) - c[x];
    //             }
    //             else {
    //                 if (y == 1)
    //                     ans += 1ll * (x - p) * (r - t) - c[x];
    //                 else
    //                     ans += 1ll * (x - p) * (l - t);
    //             }
    //             p = x;
    //             if (f) {
    //                 if (r < t)
    //                     st.insert({L, 1, t});
    //                 else
    //                     st.insert({L, 2, t});
    //                 break;
    //             }
    //         }
    //     }
    //     cout << ans << '\n';
    // }

}

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