Submission #760966

#	Time	Username	Problem	Language	Result	Execution time	Memory
760966		resting	IOI Fever (JOI21_fever)	C++17	100 / 100	3748 ms	75648 KiB

fever

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

#define int long long

const int mx = 1e5 + 5;

void solve() {
    int n; cin >> n;
    vector<pair<int, int>> p(n);
    vector<int> dir(n);
    for (auto& x : p) { cin >> x.first >> x.second; x.first *= 2; x.second *= 2; }
    int ans = 0;
    int x1 = p[0].first, x2 = p[0].second;
    for (auto& x : p) x.first -= x1, x.second -= x2;
    for (int i = 0; i < 4; i++) {
        dir[0] = 0; //u
        for (int j = 1; j < n; j++) {
            auto [x, y] = p[j];
            if (y < -abs(x)) { //d
                dir[j] = 0;
            } else if (y > abs(x)) { //u
                dir[j] = 1;
            } else if (x > abs(y)) { //l
                dir[j] = 2;
            } else if (x < -abs(y)) { //r
                dir[j] = 3;
            } else if (y < 0) { //u
                dir[j] = 0;
            } else if (x == 0) { // d
                dir[j] = 1;
            } else if (x > 0) { // l
                dir[j] = 2;
            } else if (x < 0) { //r
                dir[j] = 3;
            }
        }
        map<int, set<pair<int, int>>> a[4], b[4], c[4], d[4]; //x - y: {x, id}, x + y: {x, id}, x : {y, id}, y : {x, id}

        auto ad = [&](int dir, int x, int y, int id) {
            a[dir][x - y].insert({ x,id });
            b[dir][x + y].insert({ x,id });
            if (dir == 0 || dir == 1) c[dir][x].insert({ y, id });
            if (dir == 2 || dir == 3) d[dir][y].insert({ x, id });
        };

        auto rem = [&](int dir, int x, int y, int id) {
            a[dir][x - y].erase({ x,id });
            b[dir][x + y].erase({ x,id });
            if (dir == 0 || dir == 1) c[dir][x].erase({ y, id });
            if (dir == 2 || dir == 3) d[dir][y].erase({ x, id });
        };

        for (int j = 0; j < n; j++) {
            ad(dir[j], p[j].first, p[j].second, j);
        }

        vector<int> vis(n, 0);
        vector<vector<int>> vis2(12, vector<int>(n, 0));
        set<pair<int, pair<int, pair<int, int>>>> s; // {time, {id, prev}}

        auto add = [&](int id, int t) {
            if (id == -1) return;
            auto [x, y] = p[id];
            if (dir[id] == 0) { //u
                auto e = a[2][x - y].lower_bound({ x + t, 0 });
                if (e != a[2][x - y].end()) s.insert({ e->first - x, {e->second, {id, 0}} });

                auto f = b[3][x + y].upper_bound({ x - t, mx });
                f = (!b[3][x + y].size() || f == b[3][x + y].begin()) ? b[3][x + y].end() : prev(f);
                if (f != b[3][x + y].end()) s.insert({ x - f->first , {f->second, {id, 1}} });

                auto g = c[1][x].lower_bound({ y + t * 2, 0 });
                if (g != c[1][x].end()) s.insert({ (g->first - y) / 2, {g->second,{ id, 2}} });

            } else if (dir[id] == 1) { //d
                auto e = b[2][x + y].lower_bound({ x + t, 0 });
                if (e != b[2][x + y].end()) s.insert({ e->first - x, {e->second, {id, 3}} });

                auto f = a[3][x - y].upper_bound({ x - t, mx });
                f = (!a[3][x - y].size() || f == a[3][x - y].begin()) ? a[3][x - y].end() : prev(f);
                if (f != a[3][x - y].end()) s.insert({ x - f->first , {f->second, {id, 4}} });

                auto g = c[0][x].upper_bound({ y - t * 2, mx });
                g = (!c[0][x].size() || g == c[0][x].begin()) ? c[0][x].end() : prev(g);
                if (g != c[0][x].end()) s.insert({ (y - g->first) / 2, {g->second,{id, 5}} });

            } else if (dir[id] == 2) { //l
                auto e = a[0][x - y].upper_bound({ x - t, mx });
                e = (!a[0][x - y].size() || e == a[0][x - y].begin()) ? a[0][x - y].end() : prev(e);
                if (e != a[0][x - y].end()) s.insert({ x - e->first, {e->second, {id, 6}} });

                auto f = b[1][x + y].upper_bound({ x - t, mx });
                f = (!b[1][x + y].size() || f == b[1][x + y].begin()) ? b[1][x + y].end() : prev(f);
                if (f != b[1][x + y].end()) s.insert({ x - f->first , {f->second, {id, 7}} });

                auto g = d[3][y].upper_bound({ x - t * 2, mx });
                g = (!d[3][y].size() || g == d[3][y].begin()) ? d[3][y].end() : prev(g);
                if (g != d[3][y].end()) s.insert({ (x - g->first) / 2, {g->second, {id,8}} });

            } else { //r

                auto e = b[0][x + y].lower_bound({ x + t, 0 });
                if (e != b[0][x + y].end()) s.insert({ e->first - x, {e->second,{id, 9}} });

                auto f = a[1][x - y].lower_bound({ x + t, 0 });
                if (f != a[1][x - y].end()) s.insert({ f->first - x, {f->second,{id, 10}} });

                auto g = d[2][y].lower_bound({ x + t * 2, 0 });
                if (g != d[2][y].end()) s.insert({ (g->first - x) / 2, {g->second, {id, 11}} });
            }
        };

        s.insert({ 0, { 0, {-1, 9} } });
        int res = 0;
        while (s.size()) {
            auto [a, b] = *s.begin();
            auto [c, d] = b;
            auto [e, f] = d;
            a++;
            s.erase(s.begin());
            if (vis2[f][c]) continue;
            vis2[f][c] = 1;
            add(e, a);
            if (vis[c]) continue;
            rem(dir[c], p[c].first, p[c].second, c);
            vis[c] = 1; res++;
            add(c, a);
        }

        ans = max(ans, res);
        //rotate
        for (auto& x : p) x = { -x.second, x.first };
    }
    cout << ans << endl;
}

int32_t main() {
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
}

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