QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#913196#7917. KlompendansenzeAC ✓42ms9088kbC++201.9kb2025-02-24 12:44:532025-02-24 12:45:01

Judging History

This is the latest submission verdict.

  • [2025-02-24 12:45:01]
  • Judged
  • Verdict: AC
  • Time: 42ms
  • Memory: 9088kb
  • [2025-02-24 12:44:53]
  • Submitted

answer

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define pb push_back

const ld pi = 3.14159265358979323846;
const int mod = (int)1e9 + 7;
const ll INF = 1e18;

template<typename T>
T chmax(T a, T b) {
    return a > b ? a : b;
}

template<typename T>
T chmin(T a, T b) {
    return a > b ? b : a;
}

const int N = (int)2e5 + 1, M = N * 2;

int dir_x[4] = {1, -1, 1, -1}, dir_y[4] = {1, -1, -1, 1};

void solve(){  
    int n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;

    queue<vector<int>> q;
    int f[n + 1][n + 1][2];
    memset(f, 0, sizeof f);

    q.push({0, 0, 0});
    q.push({0, 0, 1});
    f[0][0][0] = f[0][0][1] = 1;

    while(!q.empty()){
        auto p = q.front();
        q.pop();

        int x = p[0], y = p[1], z = p[2];
        for(int i = 0; i < 4; i++){
            int dx = dir_x[i] * (z ? a : c) + x, dy = dir_y[i] * (z ? b : d) + y;
            if(dx < 0 || dy < 0 || dx >= n || dy >= n || f[dx][dy][1 - z]){
                continue;
            }
            f[dx][dy][1 - z] = 1;
            q.push({dx, dy, 1 - z});
        }

        for(int i = 0; i < 4; i++){
            int dx = dir_x[i] * (z ? b : d) + x, dy = dir_y[i] * (z ? a : c) + y;
            if(dx < 0 || dy < 0 || dx >= n || dy >= n || f[dx][dy][1 - z]){
                continue;
            }
            f[dx][dy][1 - z] = 1;
            q.push({dx, dy, 1 - z});
        }
    }

    int qwq = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            qwq += (f[i][j][0] || f[i][j][1]);
        }
    }
    cout << qwq << endl;
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    // cin >> t;

    while(t--){
        solve();
    }

    return 0;
}  

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3712kb

input:

3
2 1
2 2

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

8
1 2
1 2

output:

64

result:

ok single line: '64'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

4
1 2
2 3

output:

13

result:

ok single line: '13'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

5
1 2
2 3

output:

25

result:

ok single line: '25'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

10
3 3
4 4

output:

50

result:

ok single line: '50'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

3
1 1
1 1

output:

5

result:

ok single line: '5'

Test #7:

score: 0
Accepted
time: 0ms
memory: 5632kb

input:

500
499 499
499 499

output:

2

result:

ok single line: '2'

Test #8:

score: 0
Accepted
time: 26ms
memory: 5888kb

input:

500
1 1
1 2

output:

250000

result:

ok single line: '250000'

Test #9:

score: 0
Accepted
time: 22ms
memory: 5760kb

input:

500
250 250
250 249

output:

250000

result:

ok single line: '250000'

Test #10:

score: 0
Accepted
time: 1ms
memory: 4480kb

input:

293
52 290
100 225

output:

9

result:

ok single line: '9'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

81
1 67
38 10

output:

3057

result:

ok single line: '3057'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

49
44 9
11 45

output:

501

result:

ok single line: '501'

Test #13:

score: 0
Accepted
time: 1ms
memory: 4480kb

input:

313
220 140
166 196

output:

15467

result:

ok single line: '15467'

Test #14:

score: 0
Accepted
time: 0ms
memory: 5504kb

input:

490
268 481
286 10

output:

9

result:

ok single line: '9'

Test #15:

score: 0
Accepted
time: 0ms
memory: 5120kb

input:

411
156 396
38 119

output:

13

result:

ok single line: '13'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

19
11 16
6 15

output:

73

result:

ok single line: '73'

Test #17:

score: 0
Accepted
time: 6ms
memory: 5632kb

input:

472
29 175
273 321

output:

69211

result:

ok single line: '69211'

Test #18:

score: 0
Accepted
time: 3ms
memory: 4480kb

input:

271
228 10
242 201

output:

19004

result:

ok single line: '19004'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

78
75 77
35 6

output:

9

result:

ok single line: '9'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

71
69 65
3 9

output:

11

result:

ok single line: '11'

Test #21:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

100
98 40
9 1

output:

950

result:

ok single line: '950'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3456kb

input:

87
10 7
3 86

output:

9

result:

ok single line: '9'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

84
83 78
10 75

output:

9

result:

ok single line: '9'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

85
81 75
3 75

output:

36

result:

ok single line: '36'

Test #25:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

71
53 67
70 63

output:

7

result:

ok single line: '7'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

51
25 41
1 2

output:

1872

result:

ok single line: '1872'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

62
4 61
54 60

output:

7

result:

ok single line: '7'

Test #28:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

88
78 80
80 5

output:

352

result:

ok single line: '352'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

76
16 9
9 3

output:

5776

result:

ok single line: '5776'

Test #30:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

76
71 72
70 33

output:

9

result:

ok single line: '9'

Test #31:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

75
27 36
72 7

output:

9

result:

ok single line: '9'

Test #32:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

47
2 3
29 38

output:

716

result:

ok single line: '716'

Test #33:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

42
13 2
36 38

output:

13

result:

ok single line: '13'

Test #34:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

70
69 52
4 69

output:

23

result:

ok single line: '23'

Test #35:

score: 0
Accepted
time: 1ms
memory: 3968kb

input:

91
12 6
47 1

output:

4141

result:

ok single line: '4141'

Test #36:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

74
2 72
4 35

output:

9

result:

ok single line: '9'

Test #37:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

53
13 43
22 5

output:

2665

result:

ok single line: '2665'

Test #38:

score: 0
Accepted
time: 0ms
memory: 4224kb

input:

258
252 146
89 251

output:

218

result:

ok single line: '218'

Test #39:

score: 0
Accepted
time: 1ms
memory: 4480kb

input:

315
5 103
311 305

output:

11

result:

ok single line: '11'

Test #40:

score: 0
Accepted
time: 1ms
memory: 4352kb

input:

266
263 3
3 2

output:

4904

result:

ok single line: '4904'

Test #41:

score: 0
Accepted
time: 0ms
memory: 4864kb

input:

412
409 326
408 1

output:

80

result:

ok single line: '80'

Test #42:

score: 0
Accepted
time: 0ms
memory: 4864kb

input:

383
354 276
373 376

output:

9

result:

ok single line: '9'

Test #43:

score: 0
Accepted
time: 0ms
memory: 4352kb

input:

279
276 5
9 277

output:

44

result:

ok single line: '44'

Test #44:

score: 0
Accepted
time: 15ms
memory: 6272kb

input:

309
8 71
7 38

output:

95481

result:

ok single line: '95481'

Test #45:

score: 0
Accepted
time: 12ms
memory: 5504kb

input:

290
5 4
6 112

output:

84100

result:

ok single line: '84100'

Test #46:

score: 0
Accepted
time: 1ms
memory: 3968kb

input:

168
167 79
163 82

output:

7

result:

ok single line: '7'

Test #47:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

70
1 61
1 22

output:

3876

result:

ok single line: '3876'

Test #48:

score: 0
Accepted
time: 0ms
memory: 5504kb

input:

494
4 491
10 4

output:

25

result:

ok single line: '25'

Test #49:

score: 0
Accepted
time: 0ms
memory: 5632kb

input:

494
486 6
7 490

output:

28

result:

ok single line: '28'

Test #50:

score: 0
Accepted
time: 0ms
memory: 5632kb

input:

490
370 8
480 9

output:

5754

result:

ok single line: '5754'

Test #51:

score: 0
Accepted
time: 0ms
memory: 5504kb

input:

490
97 2
139 489

output:

13

result:

ok single line: '13'

Test #52:

score: 0
Accepted
time: 3ms
memory: 5504kb

input:

493
136 5
484 10

output:

38576

result:

ok single line: '38576'

Test #53:

score: 0
Accepted
time: 0ms
memory: 5632kb

input:

492
490 483
486 10

output:

7

result:

ok single line: '7'

Test #54:

score: 0
Accepted
time: 42ms
memory: 9088kb

input:

490
85 4
305 29

output:

240100

result:

ok single line: '240100'

Test #55:

score: 0
Accepted
time: 0ms
memory: 5632kb

input:

493
77 405
7 488

output:

9

result:

ok single line: '9'

Test #56:

score: 0
Accepted
time: 33ms
memory: 7808kb

input:

494
195 10
1 7

output:

244036

result:

ok single line: '244036'

Test #57:

score: 0
Accepted
time: 0ms
memory: 5632kb

input:

494
12 486
353 3

output:

2306

result:

ok single line: '2306'

Test #58:

score: 0
Accepted
time: 1ms
memory: 5632kb

input:

492
488 483
10 2

output:

13

result:

ok single line: '13'

Test #59:

score: 0
Accepted
time: 40ms
memory: 8960kb

input:

495
30 7
10 178

output:

245025

result:

ok single line: '245025'

Test #60:

score: 0
Accepted
time: 1ms
memory: 5760kb

input:

500
9 494
496 481

output:

26

result:

ok single line: '26'

Test #61:

score: 0
Accepted
time: 1ms
memory: 5632kb

input:

495
6 487
487 10

output:

15584

result:

ok single line: '15584'

Test #62:

score: 0
Accepted
time: 2ms
memory: 5760kb

input:

490
5 476
374 2

output:

25584

result:

ok single line: '25584'

Test #63:

score: 0
Accepted
time: 0ms
memory: 5632kb

input:

493
391 49
484 254

output:

9

result:

ok single line: '9'

Test #64:

score: 0
Accepted
time: 0ms
memory: 5632kb

input:

493
5 491
485 490

output:

23

result:

ok single line: '23'

Test #65:

score: 0
Accepted
time: 0ms
memory: 5632kb

input:

499
12 8
494 10

output:

26

result:

ok single line: '26'

Test #66:

score: 0
Accepted
time: 0ms
memory: 5760kb

input:

499
496 23
6 493

output:

9

result:

ok single line: '9'

Test #67:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

49
2 10
21 45

output:

764

result:

ok single line: '764'

Test #68:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

43
6 1
39 30

output:

348

result:

ok single line: '348'

Test #69:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

46
10 37
19 8

output:

1366

result:

ok single line: '1366'

Test #70:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

44
34 13
9 17

output:

1792

result:

ok single line: '1792'

Test #71:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

43
32 35
4 30

output:

501

result:

ok single line: '501'

Test #72:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

50
7 47
1 9

output:

602

result:

ok single line: '602'

Test #73:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

41
17 10
31 10

output:

1264

result:

ok single line: '1264'

Test #74:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

49
11 41
35 6

output:

643

result:

ok single line: '643'

Test #75:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

48
36 3
33 2

output:

1364

result:

ok single line: '1364'

Test #76:

score: 0
Accepted
time: 2ms
memory: 3968kb

input:

220
192 115
24 44

output:

33064

result:

ok single line: '33064'

Test #77:

score: 0
Accepted
time: 5ms
memory: 4480kb

input:

312
168 177
235 92

output:

69173

result:

ok single line: '69173'

Test #78:

score: 0
Accepted
time: 9ms
memory: 5120kb

input:

428
342 203
90 289

output:

115825

result:

ok single line: '115825'

Test #79:

score: 0
Accepted
time: 5ms
memory: 4608kb

input:

287
122 185
144 161

output:

68220

result:

ok single line: '68220'

Test #80:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

51
12 1
47 31

output:

425

result:

ok single line: '425'

Test #81:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

218
122 2
171 73

output:

6191

result:

ok single line: '6191'

Test #82:

score: 0
Accepted
time: 0ms
memory: 4480kb

input:

293
134 223
59 85

output:

5092

result:

ok single line: '5092'

Test #83:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

148
94 41
33 114

output:

12991

result:

ok single line: '12991'