Submission #973747

#	Time	Username	Problem	Language	Result	Execution time	Memory
973747		alextodoran	IOI Fever (JOI21_fever)	C++17	11 / 100	1 ms	2652 KiB

fever

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

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;

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

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

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

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

void go (int i, int di) {
    if (di == 0 || di == 3) {
        int dj = (di == 0 ? 1 : 2);
        int d = X[i] - Y[i];
        while (D1[d].empty() == false) {
            int j = D1[d].back();
            if (min_len[j][dj] != -1) {
                D1[d].pop_back();
            } else if (X[i] + min_len[i][di] <= X[j]) {
                D1[d].pop_back();
                min_len[j][dj] = X[j] - X[i];
                q.push(make_tuple(-min_len[j][dj], j, dj));
            } else {
                break;
            }
        }
    }
    if (di == 1 || di == 0) {
        int dj = (di == 1 ? 2 : 3);
        int d = X[i] + Y[i];
        while (D2[d].empty() == false) {
            int j = D2[d].front();
            if (min_len[j][dj] != -1) {
                D2[d].pop_front();
            } else if (X[i] - min_len[i][di] >= X[j]) {
                D2[d].pop_front();
                min_len[j][dj] = X[i] - X[j];
                q.push(make_tuple(-min_len[j][dj], j, dj));
            } else {
                break;
            }
        }
    }
    if (di == 2 || di == 1) {
        int dj = (di == 2 ? 3 : 0);
        int d = X[i] - Y[i];
        while (D1[d].empty() == false) {
            int j = D1[d].front();
            if (min_len[j][dj] != -1) {
                D1[d].pop_front();
            } else if (X[i] - min_len[i][di] >= X[j]) {
                D1[d].pop_front();
                min_len[j][dj] = X[i] - X[j];
                q.push(make_tuple(-min_len[j][dj], j, dj));
            } else {
                break;
            }
        }
    }
    if (di == 3 || di == 2) {
        int dj = (di == 3 ? 0 : 1);
        int d = X[i] + Y[i];
        while (D2[d].empty() == false) {
            int j = D2[d].back();
            if (min_len[j][dj] != -1) {
                D2[d].pop_back();
            } else if (X[i] + min_len[i][di] <= X[j]) {
                D2[d].pop_back();
                min_len[j][dj] = X[j] - X[i];
                q.push(make_tuple(-min_len[j][dj], j, dj));
            } 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 : {0, 1, 2, 3}) {
        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);
        }
        for (int i = 1; i <= N; i++) {
            for (int di : {0, 1, 2, 3}) {
                min_len[i][di] = -1;
            }
        }
        min_len[1][d1] = 0; go(1, d1);
        while (q.empty() == false) {
            int trash, i, di;
            tie(trash, i, di) = q.top();
            q.pop();
            go(i, di);
        }
        int cnt = 0;
        for (int i = 1; i <= N; i++) {
            for (int di : {0, 1, 2, 3}) {
                if (min_len[i][di] != -1) {
                    cnt++;
                    break;
                }
            }
        }
        answer = max(answer, cnt);
        D1.clear(); D2.clear();
    }
    cout << answer << "\n";

    return 0;
}

• Subtask 1: 5 / 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