Submission #760929

#	Time	Username	Problem	Language	Result	Execution time	Memory
760929		resting	IOI Fever (JOI21_fever)	C++17	0 / 100	1 ms	340 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 x1 = p[0].first, x2 = p[0].second;
    for (auto& x : p) x.first -= x1, x.second -= x2;
    int ans = 0;
    for (int i = 0; i < 4; i++) {
        cout << "roation: " << i << endl;
        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);
        set<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} });

                auto f = b[3][x + y].upper_bound({ x - t, mx });
                f = (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} });

                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} });

            } else if (dir[id] == 1) { //d
                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} });

                auto f = b[3][x - y].upper_bound({ x - t, mx });
                f = (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} });

                auto g = c[0][x].upper_bound({ y - t * 2, mx });
                g = (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} });

            } else if (dir[id] == 2) { //l
                auto e = a[0][x - y].upper_bound({ x - t, 0 });
                e = (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} });

                auto f = b[1][x + y].upper_bound({ x - t, mx });
                f = (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} });

                auto g = d[3][y].upper_bound({ x + t * 2, 0 });
                g = (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} });

            } else { //r

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

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

                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} });
            }
        };

        s.insert({ 0, { 0, -1 } });
        int res = 0;
        while (s.size()) {
            auto [a, b] = *s.begin();
            auto [c, d] = b;
            a++;
            s.erase(s.begin());
            if (vis[c]) continue;
            rem(dir[c], p[c].first, p[c].second, c);
            vis[c] = 1; res++;
            add(c, a); add(d, 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: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31