Submission #973723

#	Time	Username	Problem	Language	Result	Execution time	Memory
973723		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;

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];
int dir[N_MAX + 2];
priority_queue <pair <int, int>> q;

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

void go (int i) {
    if (dir[i] == 0 || dir[i] == 3) {
        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];
                dir[j] = (dir[i] == 0 ? 1 : 2);
                q.push({-min_len[j], j});
            } else {
                break;
            }
        }
    }
    if (dir[i] == 1 || dir[i] == 0) {
        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];
                dir[j] = (dir[i] == 1 ? 2 : 3);
                q.push({-min_len[j], j});
            } else {
                break;
            }
        }
    }
    if (dir[i] == 2 || dir[i] == 1) {
        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];
                dir[j] = (dir[i] == 2 ? 3 : 0);
                q.push({-min_len[j], j});
            } else {
                break;
            }
        }
    }
    if (dir[i] == 3 || dir[i] == 2) {
        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];
                dir[j] = (dir[i] == 3 ? 0 : 1);
                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 d : {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);
        }
        fill(min_len + 1, min_len + N + 1, -1);
        min_len[1] = 0;
        dir[1] = d; go(1);
        while (q.empty() == false) {
            int i = q.top().second; q.pop();
            go(i);
        }
        int cnt = 0;
        for (int i = 1; i <= N; i++) {
            cnt += (min_len[i] != -1);
        }
        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