QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#409991	#6776. Garden	ksu_	30	359ms	3912kb	C++23	2.5kb	2024-05-13 01:02:46	2024-05-13 01:02:47

Judging History

你现在查看的是最新测评结果

[2024-05-13 01:02:47]
评测

测评结果：30
用时：359ms
内存：3912kb

查看

[2024-05-13 01:02:46]
提交

answer

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef long long ll;

ll get(vector<ll> need, ll d){
    ll ans = d;
    sort(need.begin(), need.end());
    need.resize(unique(need.begin(), need.end()) - need.begin());
    
    ans = need.back() - need[0] + 1;
    for(int i = 0; i < need.size() - 1; i++){
        ll cnt = d - (need[i + 1] - need[i] - 1);
        ans = min(ans, cnt);
    }
    
    return ans;
}

int main(){
    ll n, m, d;
    cin >> n >> m >> d;
    
    vector<pair<ll, ll>> a(n), b(m);
    for(auto &i: a)
        cin >> i.first >> i.second;
    
    for(auto &i: b)
        cin >> i.first >> i.second;
    
    sort(a.begin(), a.end());
    a.resize(unique(a.begin(), a.end()) - a.begin());
    
    sort(b.begin(), b.end());
    b.resize(unique(b.begin(), b.end()) - b.begin());
    
    ll ans = d * d;
    for(int l = 0; l < d; l++){
        for(int r = l; r < l + d; r++){
            vector<ll> need;
            
            bool ok = false;
            for(auto j: a){
                need.push_back(j.second);
                
                if(l % d <= r % d){
                    if(j.first < l % d || j.first > r % d){
                        ok = true;
                        break;
                    }
                }
                else{
                    if(j.first <= r % d || j.first >= l % d)
                        continue;
                    
                    ok = true;
                    break;
                }
            }
            if(ok)
                continue;
            
            for(auto j: b){
                if(l % d <= r % d){
                    if(j.first >= l % d && j.first <= r % d)
                        continue;
                    
                    need.push_back(j.second);
                }
                else{
                    if(j.first <= r % d || j.first >= l % d)
                        continue;
                    
                    need.push_back(j.second);
                }
            }
            
            ll cnt = get(need, d);
            ans = min(ans, (r - l + 1) * cnt);
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

源文件, 语言: C++23

详细

Subtask #1:

score: 0

Time Limit Exceeded

Test #1:

score: 0

Time Limit Exceeded

input:

499986 5 1979
299 1572
1897 274
119 291
206 1287
816 937
1922 1376
1676 57
1106 1706
1534 176
678 606
722 473
399 727
1682 1736
221 506
1413 1857
523 1730
1699 346
1056 1287
801 1017
314 1938
1872 189
1750 581
1846 1937
37 1840
1760 725
1465 1222
678 1203
1422 1930
1273 195
730 1930
232 1666
860 352...

output:

result:

Subtask #2:

score: 6

Accepted

Test #11:

score: 6

Accepted

time: 2ms

memory: 3740kb

input:

output:

result:

ok single line: '12'

Test #12:

score: 6

Accepted

time: 1ms

memory: 3640kb

input:

1759 3239 7
5 5
2 5
3 5
3 5
2 5
1 5
3 5
4 5
5 5
1 5
3 5
5 5
2 5
5 5
5 5
2 5
4 5
1 5
1 5
4 5
2 5
3 5
1 5
4 5
5 5
1 5
2 5
1 5
1 5
3 5
4 5
2 5
1 5
2 5
5 5
2 5
2 5
4 5
3 5
2 5
4 5
5 5
5 5
2 5
3 5
4 5
1 5
2 5
4 5
3 5
3 5
3 5
4 5
5 5
3 5
3 5
1 5
5 5
1 5
3 5
1 5
5 5
4 5
3 5
5 5
3 5
4 5
2 5
5 5
2 5
2 5
2 5
...

output:

result:

ok single line: '5'

Test #13:

score: 6

Accepted

time: 2ms

memory: 3828kb

input:

output:

result:

ok single line: '10'

Test #14:

score: 6

Accepted

time: 2ms

memory: 3572kb

input:

output:

result:

ok single line: '10'

Test #15:

score: 6

Accepted

time: 1ms

memory: 3632kb

input:

output:

result:

ok single line: '9'

Test #16:

score: 6

Accepted

time: 2ms

memory: 3644kb

input:

output:

result:

ok single line: '40'

Test #17:

score: 6

Accepted

time: 2ms

memory: 3580kb

input:

output:

result:

ok single line: '70'

Test #18:

score: 6

Accepted

time: 1ms

memory: 3648kb

input:

output:

result:

ok single line: '56'

Test #19:

score: 6

Accepted

time: 0ms

memory: 3620kb

input:

output:

result:

ok single line: '100'

Test #20:

score: 6

Accepted

time: 1ms

memory: 3584kb

input:

output:

result:

ok single line: '1'

Test #21:

score: 6

Accepted

time: 1ms

memory: 3640kb

input:

output:

result:

ok single line: '2'

Subtask #3:

score: 8

Accepted

Dependency #2:

100%

Accepted

Test #22:

score: 8

Accepted

time: 3ms

memory: 3612kb

input:

2098 2896 47
18 20
23 28
6 4
5 4
29 4
21 20
24 17
7 20
21 37
7 37
44 44
23 44
18 37
7 4
4 4
5 26
29 37
16 28
14 20
38 44
29 44
24 17
24 37
21 11
29 11
5 20
5 44
23 26
2 32
7 4
14 4
6 33
7 20
2 44
3 17
16 17
20 4
14 17
16 4
44 17
3 44
16 33
7 11
4 32
18 44
3 44
21 33
23 17
2 26
18 20
4 23
16 44
16 11...

output:

result:

ok single line: '1599'

Test #23:

score: 8

Accepted

time: 2ms

memory: 3624kb

input:

2355 2645 37
24 17
10 35
10 8
24 19
1 0
1 29
20 33
3 36
3 24
1 12
24 14
20 23
10 30
10 35
10 20
3 29
10 20
10 8
24 33
10 0
10 21
24 2
20 25
24 17
1 21
10 26
20 19
1 35
10 17
3 5
24 21
3 23
10 3
24 3
3 26
20 36
24 2
1 14
1 26
3 18
10 5
10 36
20 25
20 31
3 24
3 9
24 21
24 36
10 8
24 2
10 36
10 16
1 9
...

output:

result:

ok single line: '840'

Test #24:

score: 8

Accepted

time: 36ms

memory: 3868kb

input:

output:

result:

ok single line: '50'

Test #25:

score: 8

Accepted

time: 6ms

memory: 3552kb

input:

output:

result:

ok single line: '50'

Test #26:

score: 8

Accepted

time: 3ms

memory: 3628kb

input:

output:

result:

ok single line: '47'

Test #27:

score: 8

Accepted

time: 17ms

memory: 3716kb

input:

output:

result:

ok single line: '800'

Test #28:

score: 8

Accepted

time: 3ms

memory: 3576kb

input:

output:

result:

ok single line: '1470'

Test #29:

score: 8

Accepted

time: 2ms

memory: 3612kb

input:

output:

result:

ok single line: '1443'

Test #30:

score: 8

Accepted

time: 2ms

memory: 3560kb

input:

output:

result:

ok single line: '2350'

Test #31:

score: 8

Accepted

time: 0ms

memory: 3824kb

input:

output:

result:

ok single line: '2500'

Subtask #4:

score: 16

Accepted

Dependency #3:

100%

Accepted

Test #32:

score: 16

Accepted

time: 3ms

memory: 3796kb

input:

3086 1910 47
7 32
34 32
7 28
8 32
9 17
7 28
43 10
7 32
33 13
24 15
39 10
8 15
30 19
45 15
46 15
44 13
4 28
12 10
41 19
15 13
14 17
16 15
12 17
8 13
30 17
25 10
0 19
4 0
46 13
29 28
4 33
11 17
1 19
27 17
18 0
26 17
18 0
33 0
13 15
36 32
8 17
34 13
33 10
13 10
43 17
46 19
26 32
41 15
16 33
14 17
41 10...

output:

result:

ok single line: '1496'

Test #33:

score: 16

Accepted

time: 10ms

memory: 3660kb

input:

4282 718 76
11 11
44 3
64 39
25 35
39 30
40 32
74 42
12 42
64 27
42 43
3 30
23 32
43 53
7 30
53 64
45 30
7 66
45 65
64 13
42 54
59 53
23 53
72 23
16 27
29 66
64 54
64 9
30 2
25 74
39 53
42 43
59 45
36 30
5 11
59 11
59 66
41 52
15 30
29 45
12 64
34 61
65 39
45 39
57 39
34 3
23 43
63 54
64 4
42 27
64 ...

output:

result:

ok single line: '4968'

Test #34:

score: 16

Accepted

time: 359ms

memory: 3912kb

input:

output:

result:

ok single line: '100'

Test #35:

score: 16

Accepted

time: 41ms

memory: 3628kb

input:

10 4988 100
97 33
97 33
97 33
97 33
97 33
97 33
97 33
97 33
97 33
97 33
51 3
71 12
80 23
15 10
3 82
56 7
39 15
46 40
24 31
88 99
19 45
70 61
52 5
42 56
37 27
48 48
72 68
15 21
2 73
94 39
78 63
73 86
46 53
15 21
59 15
17 91
34 4
78 63
0 63
73 86
44 22
13 60
26 35
98 70
8 13
44 84
90 78
95 48
64 84
54...

output:

result:

ok single line: '100'

Test #36:

score: 16

Accepted

time: 8ms

memory: 3776kb

input:

output:

result:

ok single line: '95'

Test #37:

score: 16

Accepted

time: 68ms

memory: 3596kb

input:

13 4982 100
32 30
71 29
71 35
32 72
33 30
33 72
24 24
71 35
71 72
33 35
32 24
3 29
24 24
76 20
29 99
70 12
0 28
78 20
56 6
18 96
7 57
41 13
30 77
51 3
60 87
27 33
15 98
9 73
78 94
58 58
91 88
47 65
2 69
83 33
2 57
7 80
66 95
83 34
78 58
56 21
17 61
56 58
10 52
2 98
0 68
38 47
36 31
63 25
21 46
93 59...

output:

result:

ok single line: '4900'

Test #38:

score: 16

Accepted

time: 8ms

memory: 3596kb

input:

10 4990 100
23 17
99 62
99 43
25 69
59 69
99 17
69 43
99 81
59 81
25 43
73 0
79 20
65 57
51 47
45 14
2 93
35 96
82 1
12 24
29 32
55 39
94 10
72 72
55 39
1 49
91 96
72 20
87 51
38 54
8 31
27 1
4 66
76 46
80 76
95 41
43 0
68 77
72 20
39 70
88 10
46 46
44 15
13 29
96 71
77 71
89 92
42 37
80 97
95 28
40...

output:

result:

ok single line: '6370'

Test #39:

score: 16

Accepted

time: 3ms

memory: 3588kb

input:

output:

result:

ok single line: '5187'

Test #40:

score: 16

Accepted

time: 50ms

memory: 3812kb

input:

14 4986 100
29 2
93 96
24 83
72 7
14 21
30 67
14 97
93 46
4 97
4 96
35 19
35 21
3 67
94 28
92 91
41 92
84 30
52 55
25 0
69 77
58 99
82 87
96 77
41 45
12 82
98 24
17 76
41 57
84 33
90 70
43 14
10 56
73 40
47 89
31 32
68 13
80 75
85 34
2 20
37 64
89 99
45 56
13 63
63 71
33 12
48 63
97 74
50 90
83 52
8...

output:

result:

ok single line: '6400'

Test #41:

score: 16

Accepted

time: 0ms

memory: 3740kb

input:

93 4907 100
0 99
84 42
16 64
26 58
71 41
89 48
97 32
52 86
53 82
22 93
14 88
59 60
74 89
80 90
13 23
98 81
85 16
83 23
94 67
92 69
67 70
45 25
96 68
27 53
69 85
82 20
64 62
30 35
3 56
68 73
21 47
55 14
31 71
6 55
50 76
24 13
2 31
19 54
39 77
93 15
40 27
11 49
87 26
63 40
12 78
66 30
34 83
17 8
43 43...

output:

result:

ok single line: '9800'

Test #42:

score: 16

Accepted

time: 3ms

memory: 3740kb

input:

105 4890 100
43 92
62 32
28 25
60 15
30 26
13 68
32 91
81 79
92 86
50 24
89 41
67 6
46 89
64 96
79 88
44 50
20 17
61 71
72 30
90 21
25 1
78 0
70 70
19 23
14 51
40 13
41 38
63 35
4 61
83 77
8 63
15 74
23 2
36 89
37 9
1 14
18 69
93 33
75 20
68 54
33 82
77 90
87 31
48 46
21 67
80 73
94 78
97 37
65 27
8...

output:

result:

ok single line: '10000'

Subtask #5:

score: 0

Time Limit Exceeded

Dependency #4:

100%

Accepted

Test #43:

score: 0

Time Limit Exceeded

input:

2177 2820 1179
466 319
573 622
600 85
945 644
562 633
938 7
927 733
1013 482
1154 741
152 1
1039 65
881 817
768 1122
1098 259
597 655
664 718
450 760
740 531
135 611
677 1010
125 1006
486 574
1178 355
29 193
1082 620
932 668
604 687
1128 335
125 166
489 935
1164 1010
945 449
538 1112
1034 1020
81 12...