Submission #71971

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 4000000000000000000 //オーバーフローに注意
#define MOD 1000000007
#define EPS 0.000000001
#define SIZE 200005
struct Info{
Info(int arg_row,int arg_col,ll arg_value){
base_row = arg_row;
base_col = arg_col;
value = arg_value;
}
bool operator<(const struct Info& arg) const{
return value < arg.value;
}
int base_row,base_col;
ll value;
};
ll N;
ll BIT[SIZE];
ll H,W,R,C,K;
ll A[405][405];
ll REV[SIZE];
map<ll,ll> MAP;
vector<Info> info;
void add(ll loc,ll value){
BIT[loc] += value;
loc += loc & -loc;
while(loc <= N){
BIT[loc] += value;
loc += loc & -loc;
}
}
ll getSum(ll loc){
if(loc == 0)return 0;
ll sum = BIT[loc];
loc -= loc & -loc;
while(loc > 0){
sum += BIT[loc];
loc -= loc & -loc;
}
return sum;
}
ll getNUM(){
ll left = 1,right = N,mid = (left+right)/2;
ll ret = -1;
while(left <= right){
ll tmp = getSum(mid);
if(tmp >= K){
ret = REV[mid];
right = mid-1;
}else{
left = mid+1;
}
mid = (left+right)/2;
}
return ret;
}
void outPut(){
sort(info.begin(),info.end());
for(ll i = 0; i < info.size(); i++){
printf("%lld\n",info[i].value);
}
}
int main(){
scanf("%lld %lld %lld %lld",&H,&W,&R,&C);
scanf("%lld",&K);
vector<ll> vec;
for(ll row = 1; row <= H; row++){
for(ll col = 1; col <= W; col++){
scanf("%lld",&A[row][col]);
vec.push_back(A[row][col]);
}
}
sort(vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
N = vec.size();
ll index = 1;
for(ll i = 0; i < vec.size(); i++){
REV[index] = vec[i];
MAP[vec[i]] = index++;
}
for(int row = 1; row <= H; row++){
for(int col = 1; col <= W; col++){
A[row][col] = MAP[A[row][col]];
}
}
for(int i = 0; i <= N; i++)BIT[i] = 0;
//まずは(1,1)
for(int row = 1; row <= R; row++){
for(int col = 1; col <= C; col++){
add(A[row][col],1);
}
}
info.push_back(Info(1,1,getNUM()));
if(H == R && W == C){
outPut();
return 0;
}
if(H == R){
for(int base_col = 2; base_col+C-1 <= W; base_col++){
//左端列の削除
for(int row = 1; row <= H; row++){
add(A[row][base_col-1],-1);
}
//右端列の追加
for(int row = 1; row <= H; row++){
add(A[row][base_col+C-1],1);
}
info.push_back(Info(1,base_col,getNUM()));
}
outPut();
return 0;
}
bool to_D = true;
int base_row = 2;
int base_col = 1;
while(base_col+C-1 <= W){
//printf("base_row:%d base_col:%d\n",base_row,base_col);
//縦に進む
if(to_D){ //下向き
while(base_row+R-1 <= H){
//上の行の削除
for(int col = base_col; col <= base_col+C-1; col++){
add(A[base_row-1][col],-1);
}
//下端の行の追加
for(int col = base_col; col <= base_col+C-1; col++){
add(A[base_row+R-1][col],1);
}
info.push_back(Info(base_row,base_col,getNUM()));
base_row++;
}
}else if(!to_D){ //上向き
while(base_row >= 1){
//上の行の追加
for(int col = base_col; col <= base_col+C-1; col++){
add(A[base_row][col],1);
}
//下端の行の削除
for(int col = base_col; col <= base_col+C-1; col++){
add(A[base_row+R][col],-1);
}
info.push_back(Info(base_row,base_col,getNUM()));
base_row--;
}
}
//右に進む
if(base_col+C-1 == W)break;
if(base_row+R-1 > H){ //下方行き止まり
base_row--;
base_col++;
//左端列の削除
for(int row = base_row; row <= base_row+R-1; row++){
add(A[row][base_col-1],-1);
}
//右端列の追加
for(int row = base_row; row <= base_row+R-1; row++){
add(A[row][base_col+C-1],1);
}
info.push_back(Info(base_row,base_col,getNUM()));
base_row--;
to_D = false;
}else{ //上方行き止まり
base_row++;
base_col++;
//左端列の削除
for(int row = base_row; row <= base_row+R-1; row++){
add(A[row][base_col-1],-1);
}
//右端列の追加
for(int row = base_row; row <= base_row+R-1; row++){
add(A[row][base_col+C-1],1);
}
info.push_back(Info(base_row,base_col,getNUM()));
base_row++;
to_D = true;
}
}
outPut();
return 0;
}

ステータス

項目 データ
問題 1544 - 決まりを守る漁師
ユーザー名 syoribu
投稿日時 2022-08-30 09:22:16
言語 C++17
状態 Accepted
得点 10
ソースコード長 4545 Byte
最大実行時間 660 ms
最大メモリ使用量 61360 KB

セット

セット 得点 Cases
1 ALL 10 / 10 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1 AC 29 ms 2652 KB
1
in2 AC 25 ms 19052 KB
1
in3 AC 24 ms 32528 KB
1
in4 AC 70 ms 48328 KB
1
in5 AC 152 ms 61360 KB
1
in6 AC 20 ms 44932 KB
1
in7 AC 27 ms 44752 KB
1
in8 AC 17 ms 44820 KB
1
in9 AC 23 ms 44756 KB
1
in10 AC 31 ms 4144 KB
1
in11 AC 49 ms 4064 KB
1
in12 AC 29 ms 4164 KB
1
in13 AC 660 ms 20436 KB
1
in14 AC 633 ms 22888 KB
1
in15 AC 229 ms 26744 KB
1
in16 AC 536 ms 29632 KB
1
in17 AC 195 ms 32460 KB
1
in18 AC 191 ms 34996 KB
1
in19 AC 309 ms 34376 KB
1
in20 AC 320 ms 36156 KB
1
in21 AC 464 ms 37192 KB
1
in22 AC 456 ms 38316 KB
1
in23 AC 377 ms 40460 KB
1
in24 AC 414 ms 41880 KB
1
in25 AC 409 ms 43432 KB
1
in26 AC 471 ms 43704 KB
1
in27 AC 329 ms 45016 KB
1
in28 AC 383 ms 46192 KB
1
in29 AC 190 ms 45964 KB
1
in30 AC 244 ms 46792 KB
1
in31 AC 187 ms 47932 KB
1
in32 AC 256 ms 50348 KB
1
in33 AC 255 ms 51660 KB
1
in34 AC 247 ms 52836 KB
1
in35 AC 58 ms 41860 KB
1
in36 AC 56 ms 42264 KB
1
in37 AC 71 ms 42676 KB
1