#2238. Rzeki

    ID: 2238 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest2022来源:qoj.ac数据:公开样例贪心

Rzeki

Rzeki

题目描述

Zadanie: RZE Rzeki XXIX OI, etap III, dzień pierwszy. Plik źródłowy rze.* Dostępna pamięć: 128 MB. 6.04.2022 Dopiero gdy zostanie ścięte ostatnie drzewo, ostatnia rzeka zatruta, a ostatnia ryba złapana, człowiek odkryje, że nie naje się pieniędzmi. – przysłowie indiańskie W Bajtocji jest n rzek płynących z południa na północ wzdłuż prostych x = i dla (i = 1, 2, . . . , n) oraz m rzek płynących z zachodu na wschód wzdłuż prostych y = j (dla j = 1, 2, . . . , m). Na każdym przecięciu rzek znajduje się miasto. W każdym mieście jedna rzeka przebiega tunelem i nie miesza się z drugą. W przeszłości każde miasto czerpało wodę z rzek, nad którymi leżało. Niestety w dzisiejszych czasach niektóre rzeki są zanieczyszczone w stopniu uniemożliwiającym uzdatnienie wody, więc miasta muszą dostarczać wodę z innych rzek. Koszt dostarczenia wody z rzeki do miasta jest równy odległości miasta od prostej, wzdłuż której płynie rzeka. Do przewozu wody używane są ciężarówki jadące dwukierunkowymi drogami położonymi wzdłuż rzek (nie ma znaczenia, w którą stronę płynie rzeka, z której do miasta dowożona jest woda). Niestety Bajtocja dysponuje ograniczonym budżetem i może nie być w stanie dostarczyć wody do wszystkich miast. Sytuację komplikuje fakt, że niektóre rzeki zostają oczyszczone, a niektóre ponownie zanieczyszczone. Napisz program, który wczyta aktualny stan rzek oraz umożliwi wykonywanie akcji dwóch typów: zmiana stanu rzeki oraz odpowiedź na zapytanie o maksymalną liczbę miast, do których da się dostarczyć wodę przy zadanym budżecie. Wejście W pierwszym wierszu wejścia podane są trzy liczby całkowite n, m i z (1 ≤n, m, z ≤100 000) oznaczające kolejno: liczbę rzek płynących w kierunku północnym, liczbę rzek płynących w kierunku wschodnim oraz liczbę akcji do przetworzenia. W drugim wierszu znajduje się słowo długości n złożone ze znaków + i - (plus i minus); i-ty znak ozna- cza stan i-tej rzeki płynącej na północ: znak plusa oznacza rzekę czystą, a znak minusa – zanieczyszczoną. W trzecim wierszu znajduje się słowo długości m opisujące początkowy stan rzek płynących na wschód, w ana- logicznym formacie. W kolejnych z wierszach znajdują się opisy akcji w jednym z następujących formatów: • Z c – zapytanie o maksymalną liczbę miast, do których można dostarczyć wodę, dysponując budżetem c (0 ≤c ≤1018), • N i – informacja że i-ta rzeka płynąca na północ zmienia swój stan, czyli jeśli była czysta, to staje się zanieczyszczona i odwrotnie (1 ≤i ≤n), • M i – informacja że i-ta rzeka płynąca na wschód zmienia swój stan (1 ≤i ≤m). Wyjście Dla każdego zapytania typu Z z wejścia należy wypisać w osobnym wierszu jedną liczbę całkowitą, oznaczającą maksymalną liczbę miast, do których będzie można doprowadzić wodę. Olimpiada Informatyczna (oi.edu.pl) 1/2 Rzeki (v. 1.2) Olimpiada Informatyczna finansowana jest ze środków Ministerstwa Edukacji Narodowej w ramach zadania publicznego „Organizacja i przeprowadzenie olimpiad i turniejów w latach szkolnych 2019/2020, 2020/2021, 2021/2022”. Przykład Dla danych wejściowych: poprawnym wynikiem jest: 3 4 11 11 --+ 9 +++- 0 Z 1 10 M 1 12 M 2 M 3 Z 7 N 3 Z 1000000000000000000 M 2 N 2 Z 4 Z 1000000000000000000 Wyjaśnienie przykładu: Poniższy rysunek obrazuje sytuację przed wykonaniem akcji. Liniami ciągłymi oznaczone są rzeki czyste, zaś liniami przerywanymi rzeki zanieczyszczone. Jest 12 miast na przecięciach tych linii. 4 3 2 1 1 2 3 Odpowiedzią dla pierwszego zapytania (Z 1) jest 11, ponieważ koszty doprowadzenia wody do miast (1, 4) oraz (2, 4) są równe 1 (stąd jedno z nich musi pozostać bez dostępu do wody), a koszty doprowadzenia wody do pozostałych dziesięciu miast są równe 0. Po wykonaniu drugiej akcji (M 1), miasta (1, 1) oraz (2, 1) tracą bezpośredni dostęp do rzeki, analogicznie po wykonaniu trzeciej i czwartej akcji bezpośredni dostęp do rzeki mają już tylko cztery miasta. A zatem odpowiedź na kolejne zapytanie (Z 7) jest równa 9, bo w ramach budżetu 7 można zapewnić dostęp do wody jeszcze czterem miastom leżącym na prostej x = 2 oraz jednemu miastu leżącemu na prostej x = 1. Testy „ocen”: 1ocen: n = m = 11, czysta jest szósta rzeka na północ i szósta rzeka na wschód; zapytania o koszty 0, 1, . . . , 220; 2ocen: n = 100 000, m = 1, przy zapytaniu zawsze jest dokładnie jedna czysta rzeka (tzn. dla 1 ≤i ≤33 333 najpierw oczyszczana jest rzeka 3i, potem następuje zapytanie o koszt 2 500 000 000, a na końcu rzeka 3i jest z powrotem zanieczyszczana). Ocenianie Zestaw testów dzieli się na następujące podzadania. Testy do każdego podzadania składają się z jednej lub więk- szej liczby osobnych grup testów. Podzadanie Warunki Liczba punktów 1 n, m, z ≤100 7 2 każda rzeka płynąca na wschód jest zawsze zanieczyszczona 7 3 n, m, z ≤1000 21 suma budżetów w zapytaniach nie przekracza 109 4 21 5 brak dodatkowych ograniczeń 44 Olimpiada Informatyczna (oi.edu.pl) 2/2 Rzeki (v. 1.2) Olimpiada Informatyczna finansowana jest ze środków Ministerstwa Edukacji Narodowej w ramach zadania publicznego „Organizacja i przeprowadzenie olimpiad i turniejów w latach szkolnych 2019/2020, 2020/2021, 2021/2022”.

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 4 11
--+
+++-
Z 1
M 1
M 2
M 3
Z 7
N 3
Z 1000000000000000000
M 2
N 2
Z 4
Z 1000000000000000000
11
9
0
10
12

样例 2

11 11 221
-----+-----
-----+-----
Z 0
Z 1
Z 2
Z 3
Z 4
Z 5
Z 6
Z 7
Z 8
Z 9
Z 10
Z 11
Z 12
Z 13
Z 14
Z 15
Z 16
Z 17
Z 18
Z 19
Z 20
Z 21
Z 22
Z 23
Z 24
Z 25
Z 26
Z 27
Z 28
Z 29
Z 30
Z 31
Z 32
Z 33
Z 34
Z 35
Z 36
Z 37
Z 38
Z 39
Z 40
Z 41
Z 42
Z 43
Z 44
Z 45
Z 46
Z 47
Z 48
Z 49
Z 50
Z 51
Z 52
Z 53
Z 54
Z 55
Z 56
Z 57
Z 58
Z 59
Z 60
Z 61
Z 62
Z 63
Z 64
Z 65
Z 66
Z 67
Z 68
Z 69
Z 70
Z 71
Z 72
Z 73
Z 74
Z 75
Z 76
Z 77
Z 78
Z 79
Z 80
Z 81
Z 82
Z 83
Z 84
Z 85
Z 86
Z 87
Z 88
Z 89
Z 90
Z 91
Z 92
Z 93
Z 94
Z 95
Z 96
Z 97
Z 98
Z 99
Z 100
Z 101
Z 102
Z 103
Z 104
Z 105
Z 106
Z 107
Z 108
Z 109
Z 110
Z 111
Z 112
Z 113
Z 114
Z 115
Z 116
Z 117
Z 118
Z 119
Z 120
Z 121
Z 122
Z 123
Z 124
Z 125
Z 126
Z 127
Z 128
Z 129
Z 130
Z 131
Z 132
Z 133
Z 134
Z 135
Z 136
Z 137
Z 138
Z 139
Z 140
Z 141
Z 142
Z 143
Z 144
Z 145
Z 146
Z 147
Z 148
Z 149
Z 150
Z 151
Z 152
Z 153
Z 154
Z 155
Z 156
Z 157
Z 158
Z 159
Z 160
Z 161
Z 162
Z 163
Z 164
Z 165
Z 166
Z 167
Z 168
Z 169
Z 170
Z 171
Z 172
Z 173
Z 174
Z 175
Z 176
Z 177
Z 178
Z 179
Z 180
Z 181
Z 182
Z 183
Z 184
Z 185
Z 186
Z 187
Z 188
Z 189
Z 190
Z 191
Z 192
Z 193
Z 194
Z 195
Z 196
Z 197
Z 198
Z 199
Z 200
Z 201
Z 202
Z 203
Z 204
Z 205
Z 206
Z 207
Z 208
Z 209
Z 210
Z 211
Z 212
Z 213
Z 214
Z 215
Z 216
Z 217
Z 218
Z 219
Z 220
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
57
58
58
59
59
60
60
61
61
62
62
63
63
64
64
65
65
66
66
67
67
68
68
69
69
70
70
71
71
72
72
73
73
74
74
75
75
76
76
77
77
78
78
79
79
80
80
81
81
82
82
83
83
84
84
85
85
85
86
86
86
87
87
87
88
88
88
89
89
89
90
90
90
91
91
91
92
92
92
93
93
93
94
94
94
95
95
95
96
96
96
97
97
97
98
98
98
99
99
99
100
100
100
101
101
101
102
102
102
103
103
103
104
104
104
105
105
105
105
106
106
106
106
107
107
107
107
108
108
108
108
109
109
109
109
110
110
110
110
111
111
111
111
112
112
112
112
113
113
113
113
114
114
114
114
115
115
115
115
116
116
116
116
117
117
117
117
117
118
118
118
118
118
119
119
119
119
119
120
120
120
120
120
121