Submission #677514

#	Time	Username	Problem	Language	Result	Execution time	Memory
677514		mjhmjh1104	방벽 (JOI15_walls)	C++17	100 / 100	753 ms	28876 KiB

walls

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

const bool debug = false;

struct Item {
    int a;
    int b;
    int i;
    int fi;
    int se;
    bool operator< (const Item &O) const {
        return b - a < O.b - O.a;
    }
};

pair<long long, long long> operator+ (const pair<long long, long long> &a, const pair<long long, long long> &b) {
    return { a.first + b.first, a.second + b.second };
}

pair<long long, long long> lazy1[524288], lazy2[524288];

void propagate1(int i, int b, int e) {
    if (b != e) {
        lazy1[i * 2 + 1] = lazy1[i * 2 + 1] + lazy1[i];
        lazy1[i * 2 + 2] = lazy1[i * 2 + 2] + lazy1[i];
        lazy1[i] = { 0, 0 };
    }
}

pair<long long, long long> query1(int i, int b, int e, int p) {
    propagate1(i, b, e);
    if (p < b || e < p) return { 0, 0 };
    if (b == e) return lazy1[i];
    int m = (b + e) / 2;
    return query1(i * 2 + 1, b, m, p) + query1(i * 2 + 2, m + 1, e, p);
}

void substitute1(int i, int b, int e, int p, long long v) {
    propagate1(i, b, e);
    if (p < b || e < p) return;
    if (b == e) {
        lazy1[i] = { v, 0 };
        return;
    }
    int m = (b + e) / 2;
    substitute1(i * 2 + 1, b, m, p, v);
    substitute1(i * 2 + 2, m + 1, e, p, v);
}

void update1(int i, int b, int e, int l, int r, long long v1, long long v2) {
    propagate1(i, b, e);
    if (r < l || r < b || e < l) return;
    if (l <= b && e <= r) {
        lazy1[i] = lazy1[i] + make_pair(v1, v2);
        return;
    }
    int m = (b + e) / 2;
    update1(i * 2 + 1, b, m, l, r, v1, v2);
    update1(i * 2 + 2, m + 1, e, l, r, v1, v2);
}

void propagate2(int i, int b, int e) {
    if (b != e) {
        lazy2[i * 2 + 1] = lazy2[i * 2 + 1] + lazy2[i];
        lazy2[i * 2 + 2] = lazy2[i * 2 + 2] + lazy2[i];
    lazy2[i] = { 0, 0 };
    }
}

pair<long long, long long> query2(int i, int b, int e, int p) {
    propagate2(i, b, e);
    if (p < b || e < p) return { 0, 0 };
    if (b == e) return lazy2[i];
    int m = (b + e) / 2;
    return query2(i * 2 + 1, b, m, p) + query2(i * 2 + 2, m + 1, e, p);
}

void substitute2(int i, int b, int e, int p, long long v) {
    propagate2(i, b, e);
    if (p < b || e < p) return;
    if (b == e) {
        lazy2[i] = { v, 0 };
        return;
    }
    int m = (b + e) / 2;
    substitute2(i * 2 + 1, b, m, p, v);
    substitute2(i * 2 + 2, m + 1, e, p, v);
}

void update2(int i, int b, int e, int l, int r, long long v1, long long v2) {
    propagate2(i, b, e);
    if (r < l || r < b || e < l) return;
    if (l <= b && e <= r) {
        lazy2[i] = lazy2[i] + make_pair(v1, v2);
        return;
    }
    int m = (b + e) / 2;
    update2(i * 2 + 1, b, m, l, r, v1, v2);
    update2(i * 2 + 2, m + 1, e, l, r, v1, v2);
}

long long query1(int x, int l) {
    pair<long long, long long> t = query1(0, 0, 262143, x);
    return t.first + t.second * l;
}

long long query2(int x, int l) {
    pair<long long, long long> t = query2(0, 0, 262143, x);
    return t.first + t.second * l;
}

void update1(int p, long long v) {
    substitute1(0, 0, 262143, p, v);
}

void update2(int p, long long v) {
    substitute2(0, 0, 262143, p, v);
}

void update1(int l, int r, long long uA, long long uB) {
    update1(0, 0, 262143, l, r, uA, uB);
}

void update2(int l, int r, long long uA, long long uB) {
    update2(0, 0, 262143, l, r, uA, uB);
}

void update(int l, int r, long long uA, long long uB, int y) {
    if (debug) printf("UPDATE: [%d,%d], %lld, %lld\n", l, r, uA, uB);
    if (y) update2(l, r, uA, uB);
    else update1(l, r, uA, uB);
}

int n, m, p[200006];
vector<Item> v, v1, v2;
long long res[200006];

// stick, x, [l, r]

void sum_left(int s, int x, int l, int r, int y) {
    if (debug) puts("SUM_LEFT");
    if (x <= s) update(l, r, s - x, 0, y);
    else update(l, r, x - s, -1, y);
}

void sum_right(int s, int x, int l, int r, int y) {
    if (debug) puts("SUM_RIGHT");
    if (x >= s) update(l, r, x - s, 0, y);
    else update(l, r, s - x, -1, y);
}

void process(vector<Item> &v, vector<pair<int, pair<int, bool>>> &st, int x, int y) {
    if (debug) puts("PROCESS");
    if (v.empty()) return;
    int n = (int)v.size();
    int a = v[0].a, b = v[0].b;
    if (st.back().second.second) {
        a = st.back().first;
        b = a + (v[0].b - v[0].a);
    } else {
        b = st.back().first;
        a = b - (v[0].b - v[0].a);
    }
    if (a <= x && x <= b) return;
    int l = 0, r = n - 1;
    while (l < r) {
        int m = (l + r + 1) / 2;
        int a, b;
        {
            int L = 0, R = (int)st.size() - 1;
            while (L < R) {
                int M = (L + R + 1) / 2;
                if (st[M].second.first >= m) L = M;
                else R = M - 1;
            }
            if (st[L].second.second) {
                a = st[L].first;
                b = a + (v[m].b - v[m].a);
            } else {
                b = st[L].first;
                a = b - (v[m].b - v[m].a);
            }
        }
        if (a <= x && x <= b) r = m - 1;
        else l = m;
    }
    if (debug) printf("! SIZE=%d\n", (int)st.size());
    int k = (int)st.size() - 1, lt = 0;
    while (k >= 0 && st[k].second.first <= l) {
        if (st[k].second.second) sum_left(st[k].first, x, lt, st[k].second.first, y);
        else sum_right(st[k].first, x, lt, st[k].second.first, y);
        lt = st[k].second.first + 1;
        k--;
        st.pop_back();
    }
    if (k >= 0) {
        if (st[k].second.second) sum_left(st[k].first, x, lt, l, y);
        else sum_right(st[k].first, x, lt, l, y);
    }
    if (x < a) st.push_back({ x, { l, true } });
    else st.push_back({ x, { l, false } });
    if (debug) {
        printf("lt=%d, l=%d\n", lt, l);
        puts("st:");
        for (auto &i: st) printf("%d / %d / %d\n", i.first, i.second.first, i.second.second ? 1 : 0);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    v.resize(n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &v[i].a, &v[i].b);
        v[i].i = i;
        v[i].fi = v[i].se = (int)1e9;
    }
    for (int i = 0; i < m; i++) scanf("%d", p + i);

    vector<pair<int, int>> queries1, queries2;
    vector<pair<int, pair<bool, int>>> queries;
    for (int i = 0; i < n; i++) {
        // v[i].a 미만 중 첫번: v[i].fi
        queries1.push_back({ v[i].a, i });
        // v[i].b 초과 중 첫번: v[i].se
        queries2.push_back({ v[i].b, i });
    }
    {
        sort(queries1.rbegin(), queries1.rend());
        int k = 0;
        for (int i = 0; i < m; i++) {
            while (k < (int)queries1.size() && p[i] < queries1[k].first) {
                v[queries1[k].second].fi = i;
                k++;
            }
        }
    }
    {
        sort(queries2.begin(), queries2.end());
        int k = 0;
        for (int i = 0; i < m; i++) {
            while (k < (int)queries2.size() && p[i] > queries2[k].first) {
                v[queries2[k].second].se = i;
                k++;
            }
        }
    }

    sort(v.begin(), v.end());
    for (auto &i: v) {
        if (i.fi < i.se) {
            queries.push_back({ i.fi, { true, (int)v1.size() } });
            v1.push_back(i);
        }
        if (i.fi > i.se) {
            queries.push_back({ i.se, { false, (int)v2.size() } });
            v2.push_back(i);
        }
    }
    sort(queries.begin(), queries.end());
    vector<pair<int, pair<int, bool>>> st1, st2; // pos, idx, stick to left?
    st1.push_back({ (int)1e9, { n - 1, true } });
    st2.push_back({ (int)-1e9, { n - 1, false } });

    if (debug) printf("v1=%d / v2=%d\n", (int)v1.size(), (int)v2.size());

    int k = 0;
    for (int i = 0; i < m; i++) {
        process(v1, st1, p[i], 0);
        process(v2, st2, p[i], 1);
        while (k < (int)queries.size() && queries[k].first <= i) {
            if (queries[k].second.first) update1(queries[k].second.second, v1[queries[k].second.second].a - p[i]);
            else update2(queries[k].second.second, p[i] - v2[queries[k].second.second].b);
            k++;
        }
    }
    for (int i = 0; i < (int)v1.size(); i++) res[v1[i].i] = query1(i, v1[i].b - v1[i].a);
    for (int i = 0; i < (int)v2.size(); i++) res[v2[i].i] = query2(i, v2[i].b - v2[i].a);
    sort(v.begin(), v.end(), [](const Item &a, const Item &b) {
        return a.i < b.i;
    });
    for (int i = 0; i < n; i++) {
        if (debug) printf("\nFI=%d / SE=%d\n", v[i].fi, v[i].se);
        if (v[i].fi == (int)1e9 && v[i].se == (int)1e9) puts("0");
        else printf("%lld\n", res[i]);
    }
}

Compilation message (stderr)

walls.cpp: In function 'int main()':
walls.cpp:214:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  214 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
walls.cpp:217:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  217 |         scanf("%d%d", &v[i].a, &v[i].b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
walls.cpp:221:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  221 |     for (int i = 0; i < m; i++) scanf("%d", p + i);
      |                                 ~~~~~^~~~~~~~~~~~~

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