oj.uz

Submission #973723

# Submission time Handle Problem Language Result Execution time Memory
973723 2024-05-02T10:10:15 Z alextodoran IOI Fever (JOI21_fever) C++17
19 / 100
 1 ms 604 KB 
/**
 _  _   __  _ _ _  _  _ _
 |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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 452 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 452 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 476 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 344 KB Output is correct
43 Correct 0 ms 468 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 472 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 452 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 476 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 344 KB Output is correct
43 Correct 0 ms 468 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 1 ms 344 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 1 ms 472 KB Output is correct
50 Correct 1 ms 604 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 1 ms 344 KB Output is correct
55 Correct 1 ms 348 KB Output is correct
56 Correct 0 ms 604 KB Output is correct
57 Correct 0 ms 600 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 344 KB Output is correct
61 Correct 1 ms 348 KB Output is correct
62 Correct 0 ms 348 KB Output is correct
63 Correct 0 ms 348 KB Output is correct
64 Correct 1 ms 348 KB Output is correct
65 Incorrect 1 ms 348 KB Output isn't correct
66 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 452 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 476 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 344 KB Output is correct
43 Correct 0 ms 468 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 1 ms 344 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 1 ms 472 KB Output is correct
50 Correct 1 ms 604 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 1 ms 344 KB Output is correct
55 Correct 1 ms 348 KB Output is correct
56 Correct 0 ms 604 KB Output is correct
57 Correct 0 ms 600 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 344 KB Output is correct
61 Correct 1 ms 348 KB Output is correct
62 Correct 0 ms 348 KB Output is correct
63 Correct 0 ms 348 KB Output is correct
64 Correct 1 ms 348 KB Output is correct
65 Incorrect 1 ms 348 KB Output isn't correct
66 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 452 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 476 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 344 KB Output is correct
43 Correct 0 ms 468 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 1 ms 344 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 1 ms 472 KB Output is correct
50 Correct 1 ms 604 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 1 ms 344 KB Output is correct
55 Correct 1 ms 348 KB Output is correct
56 Correct 0 ms 604 KB Output is correct
57 Correct 0 ms 600 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 344 KB Output is correct
61 Correct 1 ms 348 KB Output is correct
62 Correct 0 ms 348 KB Output is correct
63 Correct 0 ms 348 KB Output is correct
64 Correct 1 ms 348 KB Output is correct
65 Incorrect 1 ms 348 KB Output isn't correct
66 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 452 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 0 ms 476 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 344 KB Output is correct
43 Correct 0 ms 468 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 1 ms 344 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 1 ms 472 KB Output is correct
50 Correct 1 ms 604 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 1 ms 344 KB Output is correct
55 Correct 1 ms 348 KB Output is correct
56 Correct 0 ms 604 KB Output is correct
57 Correct 0 ms 600 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 344 KB Output is correct
61 Correct 1 ms 348 KB Output is correct
62 Correct 0 ms 348 KB Output is correct
63 Correct 0 ms 348 KB Output is correct
64 Correct 1 ms 348 KB Output is correct
65 Incorrect 1 ms 348 KB Output isn't correct
66 Halted 0 ms 0 KB -