Submission #933829

#	Time	Username	Problem	Language	Result	Execution time	Memory
933829		Pannda	IOI Fever (JOI21_fever)	C++17	6 / 100	1 ms	420 KiB

fever

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

#define int long long

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<array<int, 2>> a(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        x *= 2;
        y *= 2;
        a[i] = {x, y};
    }

    // directions are 0.up 1.down 2.left 3.right
    auto solve = [](int n, vector<array<int, 2>> a, int dir0) -> int {
        map<int, set<array<int, 2>>> mp_hor, mp_ver, mp_up, mp_down;
        for (int i = 1; i < n; i++) {
            auto [x, y] = a[i];
            mp_up[y - x].insert({x, i});
            mp_down[y + x].insert({x, i});
            mp_hor[y].insert({x, i});
            mp_ver[x].insert({y, i});
        }
        queue<array<int, 3>> que;
        vector<bool> vis(n, false);
        que.push({0, dir0, 0});
        vis[0] = true;
        while (!que.empty()) {
            auto [i, dir, d] = que.front();
            auto [x, y] = a[i];
//            cout << x / 2 << ' ' << y / 2 << ' ' << dir << ' ' << d << '\n';
            que.pop();

            if (dir == 0) {
                {
                    auto it = mp_ver.find(x);
                    if (it != mp_ver.end()) {
                        while (!it->second.empty()) {
                            auto [yy, ii] = *prev(it->second.end());
                            if (vis[ii]) {
                                it->second.erase(prev(it->second.end()));
                                continue;
                            }
                            if (yy >= y + 2 * d) {
                                it->second.erase(prev(it->second.end()));
                                vis[ii] = true;
                                que.push({ii, 1, abs(y - yy) / 2});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_ver.erase(it);
                    }
                }
                {
                    auto it = mp_up.find(y - x);
                    if (it != mp_up.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *prev(it->second.end());
                            if (vis[ii]) {
                                it->second.erase(prev(it->second.end()));
                                continue;
                            }
                            if (xx >= x + d) {
                                it->second.erase(prev(it->second.end()));
                                vis[ii] = true;
                                que.push({ii, 2, abs(x - xx)});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_up.erase(it);
                    }
                }
                {
                    auto it = mp_down.find(y + x);
                    if (it != mp_down.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *(it->second.begin());
                            if (vis[ii]) {
                                it->second.erase(it->second.begin());
                                continue;
                            }
                            if (xx <= x - d) {
                                it->second.erase(it->second.begin());
                                vis[ii] = true;
                                que.push({ii, 3, abs(x - xx)});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_down.erase(it);
                    }
                }
            }

            if (dir == 1) {
                {
                    auto it = mp_ver.find(x);
                    if (it != mp_ver.end()) {
                        while (!it->second.empty()) {
                            auto [yy, ii] = *(it->second.begin());
                            if (vis[ii]) {
                                it->second.erase(it->second.begin());
                                continue;
                            }
                            if (yy <= y - 2 * d) {
                                it->second.erase(it->second.begin());
                                vis[ii] = true;
                                que.push({ii, 0, abs(y - yy) / 2});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_ver.erase(it);
                    }
                }
                {
                    auto it = mp_up.find(y - x);
                    if (it != mp_up.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *(it->second.begin());
                            if (vis[ii]) {
                                it->second.erase(it->second.begin());
                                continue;
                            }
                            if (xx <= x - d) {
                                it->second.erase(it->second.begin());
                                vis[ii] = true;
                                que.push({ii, 3, abs(x - xx)});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_up.erase(it);
                    }
                }
                {
                    auto it = mp_down.find(y + x);
                    if (it != mp_down.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *prev(it->second.end());
                            if (vis[ii]) {
                                it->second.erase(prev(it->second.end()));
                                continue;
                            }
                            if (xx >= x + d) {
                                it->second.erase(prev(it->second.end()));
                                vis[ii] = true;
                                que.push({ii, 2, abs(x - xx)});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_down.erase(it);
                    }
                }
            }

            if (dir == 2) {
                {
                    auto it = mp_hor.find(y);
                    if (it != mp_hor.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *(it->second.begin());
                            if (vis[ii]) {
                                it->second.erase(it->second.begin());
                                continue;
                            }
                            if (xx <= x - 2 * d) {
                                it->second.erase(it->second.begin());
                                vis[ii] = true;
                                que.push({ii, 3, abs(x - xx) / 2});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_hor.erase(it);
                    }
                }
                {
                    auto it = mp_up.find(y - x);
                    if (it != mp_up.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *(it->second.begin());
                            if (vis[ii]) {
                                it->second.erase(it->second.begin());
                                continue;
                            }
                            if (xx <= x - d) {
                                it->second.erase(it->second.begin());
                                vis[ii] = true;
                                que.push({ii, 0, abs(x - xx)});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_up.erase(it);
                    }
                }
                {
                    auto it = mp_down.find(y + x);
                    if (it != mp_down.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *(it->second.begin());
                            if (vis[ii]) {
                                it->second.erase(it->second.begin());
                                continue;
                            }
                            if (xx <= x - d) {
                                it->second.erase(it->second.begin());
                                vis[ii] = true;
                                que.push({ii, 1, abs(x - xx)});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_down.erase(it);
                    }
                }
            }

            if (dir == 3) {
                {
                    auto it = mp_hor.find(y);
                    if (it != mp_hor.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *prev(it->second.end());
                            if (vis[ii]) {
                                it->second.erase(prev(it->second.end()));
                                continue;
                            }
                            if (xx >= x + 2 * d) {
                                it->second.erase(prev(it->second.end()));
                                vis[ii] = true;
                                que.push({ii, 2, abs(x - xx) / 2});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_hor.erase(it);
                    }
                }
                {
                    auto it = mp_up.find(y - x);
                    if (it != mp_up.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *prev(it->second.end());
                            if (vis[ii]) {
                                it->second.erase(prev(it->second.end()));
                                continue;
                            }
                            if (xx >= x + d) {
                                it->second.erase(prev(it->second.end()));
                                vis[ii] = true;
                                que.push({ii, 1, abs(x - xx)});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_up.erase(it);
                    }
                }
                {
                    auto it = mp_down.find(y + x);
                    if (it != mp_down.end()) {
                        while (!it->second.empty()) {
                            auto [xx, ii] = *prev(it->second.end());
                            if (vis[ii]) {
                                it->second.erase(prev(it->second.end()));
                                continue;
                            }
                            if (xx >= x + d) {
                                it->second.erase(prev(it->second.end()));
                                vis[ii] = true;
                                que.push({ii, 0, abs(x - xx)});
                                continue;
                            }
                            break;
                        }
                        if (it->second.empty()) mp_down.erase(it);
                    }
                }
            }
        }
        return count(vis.begin(), vis.end(), true);
    };

    cout << max({solve(n, a, 0), solve(n, a, 1), solve(n, a, 2), solve(n, a, 3)}) << '\n';
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31