Submission #718729

#	Time	Username	Problem	Language	Result	Execution time	Memory
718729		Cyanmond	Arcade (NOI20_arcade)	C++17	100 / 100	496 ms	48312 KiB

Arcade

#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 inf = 1ll << 60;

using F = std::pair<i64, int>;
F op(F a, F b) {
    return std::min(a, b);
}
F e() {
    return {inf, 0};
}

struct SegTree {
    int n, size;
    std::vector<F> data;

    SegTree(const std::vector<F> &vec) : n(vec.size()) {
        size = 1;
        while (size < n) size *= 2;
        data.assign(2 * size, e());
        std::copy(vec.begin(), vec.end(), data.begin() + size);
        for (int i = size - 1; i >= 1; --i) data[i] = op(data[2 * i], data[2 * i + 1]);
    }

    void set(int i, const F &v) {
        i += size;
        data[i] = v;
        while (i != 1) {
            i /= 2;
            data[i] = op(data[2 * i], data[2 * i + 1]);
        }
    }

    F fold(int l, int r) {
        l += size;
        r += size;
        F ret = e();
        while (l < r) {
            if (l & 1) ret = op(ret, data[l++]);
            if (r & 1) ret = op(ret, data[--r]);
            l /= 2;
            r /= 2;
        }
        return ret;
    }
};

void solve() {
    i64 N;
    int M;
    std::cin >> N >> M;
    std::vector<i64> T(M), A(M);
    for (auto &e : T) std::cin >> e;
    for (auto &e : A) std::cin >> e;

    std::vector<std::pair<i64, i64>> points(M);
    for (int i = 0; i < M; ++i) {
        points[i] = {T[i] + A[i], T[i] - A[i]};
    }
    std::sort(points.begin(), points.end());
    std::vector<std::pair<i64, int>> initVec(M);
    for (int i = 0; i < M; ++i) {
        initVec[i] = {points[i].second, i};
    }

    SegTree seg(initVec);
    int answer = 0;
    while (seg.fold(0, M) != e()) {
        ++answer;
        int l = 0;
        while (true) {
            const auto mn = seg.fold(l, M);
            if (mn.first == inf) break;
            seg.set(mn.second, e());
            l = mn.second;
        }
    }
    std::cout << answer << std::endl;
}

int main() {
    int T;
    // std::cin >> T;
    T = 1;
    while (T--) {
        solve();
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 14 / 14
• Subtask 6: 20 / 20
• Subtask 7: 15 / 15