Submission #973800

#	Time	Username	Problem	Language	Result	Execution time	Memory
973800		alextodoran	IOI Fever (JOI21_fever)	C++17	19 / 100	1 ms	604 KiB

fever

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;

const int UP = 0, LEFT = 1, DOWN = 2, RIGHT = 3;

int N;
int X[N_MAX + 2], Y[N_MAX + 2];
int order[N_MAX + 2];

unordered_map <int, deque <int>> D1, D2;

int dir[N_MAX + 2];

int min_len[N_MAX + 2];
priority_queue <pair <int, int>> q;

/*
   1\ 0 /0
     \|/
    1-x-3
     /|\
   2/ 2 \3
*/

void go (int i) {
    if (dir[i] == UP || dir[i] == RIGHT) {
        int d = X[i] - Y[i];
        while (D1[d].empty() == false) {
            int j = D1[d].back();
            if (min_len[j] != -1) {
                D1[d].pop_back();
            } else if (X[i] + min_len[i] <= X[j]) {
                D1[d].pop_back();
                min_len[j] = X[j] - X[i];
                q.push({-min_len[j], j});
            } else {
                break;
            }
        }
    }
    if (dir[i] == LEFT || dir[i] == UP) {
        int d = X[i] + Y[i];
        while (D2[d].empty() == false) {
            int j = D2[d].front();
            if (min_len[j] != -1) {
                D2[d].pop_front();
            } else if (X[i] - min_len[i] >= X[j]) {
                D2[d].pop_front();
                min_len[j] = X[i] - X[j];
                q.push({-min_len[j], j});
            } else {
                break;
            }
        }
    }
    if (dir[i] == DOWN || dir[i] == LEFT) {
        int d = X[i] - Y[i];
        while (D1[d].empty() == false) {
            int j = D1[d].front();
            if (min_len[j] != -1) {
                D1[d].pop_front();
            } else if (X[i] - min_len[i] >= X[j]) {
                D1[d].pop_front();
                min_len[j] = X[i] - X[j];
                q.push({-min_len[j], j});
            } else {
                break;
            }
        }
    }
    if (dir[i] == RIGHT || dir[i] == DOWN) {
        int d = X[i] + Y[i];
        while (D2[d].empty() == false) {
            int j = D2[d].back();
            if (min_len[j] != -1) {
                D2[d].pop_back();
            } else if (X[i] + min_len[i] <= X[j]) {
                D2[d].pop_back();
                min_len[j] = X[j] - X[i];
                q.push({-min_len[j], j});
            } else {
                break;
            }
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> X[i] >> Y[i];
    }
    iota(order + 1, order + N + 1, 1);
    sort(order + 1, order + N + 1, [&] (const int &i, const int &j) {
        return X[i] < X[j];
    });
    int answer = 0;
    for (int d1 : {UP, LEFT, DOWN, RIGHT}) {
        for (int k = 1; k <= N; k++) {
            int i = order[k];
            D1[X[i] - Y[i]].push_back(i);
            D2[X[i] + Y[i]].push_back(i);
        }
        dir[1] = d1;
        for (int i = 2; i <= N; i++) {
            if (abs(X[i] - X[1]) > abs(Y[i] - Y[1])) {
                dir[i] = (X[i] < X[1] ? RIGHT : LEFT);
            } else if (abs(Y[i] - Y[1]) > abs(X[i] - X[1])) {
                dir[i] = (Y[i] < Y[1] ? UP : DOWN);
            } else {
                if (d1 == UP) {
                    if (Y[i] < Y[1]) {
                        dir[i] = UP;
                    } else {
                        dir[i] = (X[i] < X[1] ? RIGHT : LEFT);
                    }
                }
                if (d1 == LEFT) {
                    if (X[i] > X[1]) {
                        dir[i] = LEFT;
                    } else {
                        dir[i] = (Y[i] < Y[1] ? UP : DOWN);
                    }
                }
                if (d1 == DOWN) {
                    if (Y[i] > Y[1]) {
                        dir[i] = DOWN;
                    } else {
                        dir[i] = (X[i] < X[1] ? RIGHT : LEFT);
                    }
                }
                if (d1 == RIGHT) {
                    if (X[i] < X[1]) {
                        dir[i] = RIGHT;
                    } else {
                        dir[i] = (Y[i] < Y[1] ? UP : DOWN);
                    }
                }
            }
        }
        fill(min_len + 1, min_len + N + 1, -1);
        min_len[1] = 0; go(1);
        int cnt = 1;
        while (q.empty() == false) {
            int i = q.top().second;
            q.pop();
            cnt++;
            go(i);
        }
        answer = max(answer, cnt);
        D1.clear(); D2.clear();
    }
    cout << answer << "\n";

    return 0;
}

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