Submission #950421

#	Time	Username	Problem	Language	Result	Execution time	Memory
950421		arbuzick	Cell Automaton (JOI23_cell)	C++17	32 / 100	4514 ms	2097152 KiB

cell

#include <bits/stdc++.h>
#define int long long

using namespace std;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<pair<int, int>> xy(n);
    bool check = true;
    for (int i = 0; i < n; ++i) {
        cin >> xy[i].first >> xy[i].second;
        if (xy[i].first != xy[i].second) {
            check = false;
        }
    }
    vector<int> t(q);
    for (int i = 0; i < q; ++i) {
        cin >> t[i];
    }
    if (!check) {
        vector<int> ans(t[q - 1] + 1);
        ans[0] = xy.size();
        set<pair<int, int>> black, gray;
        for (int i = 0; i < n; ++i) {
            black.insert(xy[i]);
        }
        for (int i = 1; i <= t[q - 1]; ++i) {
            set<pair<int, int>> black_nw;
            for (auto [x, y] : black) {
                if (!black.count({x + 1, y}) && !gray.count({x + 1, y})) {
                    black_nw.emplace(x + 1, y);
                }
                if (!black.count({x - 1, y}) && !gray.count({x - 1, y})) {
                    black_nw.emplace(x - 1, y);
                }
                if (!black.count({x, y + 1}) && !gray.count({x, y + 1})) {
                    black_nw.emplace(x, y + 1);
                }
                if (!black.count({x, y - 1}) && !gray.count({x, y - 1})) {
                    black_nw.emplace(x, y - 1);
                }
            }
            gray = black;
            black = black_nw;
            ans[i] = black.size();
        }
        for (int i = 0; i < q; ++i) {
            cout << ans[t[i]] << '\n';
        }
    } else {
        sort(xy.begin(), xy.end());
        vector<pair<int, int>> tms;
        for (int i = 0; i < q; ++i) {
            tms.emplace_back(t[i], n);
        }
        for (int i = 0; i + 1 < n; ++i) {
            tms.emplace_back(xy[i + 1].first - xy[i].first, i);
            tms.emplace_back(xy[i + 1].first - xy[i].first + 1, i);
        }
        sort(tms.begin(), tms.end());
        map<int, long long> ans;
        set<pair<int, int>> segms;
        for (int i = 0; i < n; ++i) {
            segms.emplace(i, i + 1);
        }
        int cntp = 0;
        long long sum_segms = 0;
        for (auto [t, ind] : tms) {
            if (ind < n) {
                if (t == xy[ind + 1].first - xy[ind].first) {
                    auto it = segms.lower_bound(make_pair(ind + 1, -1));
                    int r = it->second;
                    sum_segms -= xy[it->second - 1].first - xy[it->first].first;
                    it--;
                    int l = it->first;
                    sum_segms -= xy[it->second - 1].first - xy[it->first].first;
                    segms.erase(segms.lower_bound(make_pair(l, -1)));
                    segms.erase(segms.lower_bound(make_pair(ind + 1, -1)));
                    segms.emplace(l, r);
                    sum_segms += xy[r - 1].first - xy[l].first;
                    cntp++;
                } else {
                    cntp--;
                }
            } else {
                ans[t] = 0;
                if (t == 0) {
                    ans[t] = n;
                } else {
                    ans[t] += sum_segms * 2;
                    ans[t] += segms.size() * 1LL * (t + 1) * 2;
                    ans[t] += segms.size() * 1LL * (t - 1) * 2;
                    ans[t] += cntp * 1LL * (t - 1);
                }
            }
        }
        for (int i = 0; i < q; ++i) {
            cout << ans[t[i]] << '\n';
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 26