UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#213390#2068. 最长公共前缀ThySecret10025048ms99412kbC++113.2kb2024-11-11 21:19:362024-11-11 23:06:00

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long
// #define x first
// #define y second
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

inline void debug() { cerr << '\n'; }
template<typename Type, typename... Other>
inline void debug(const Type& x, const Other&... y) { cerr << x << ' '; debug(y...); }
#define DEBUG(a...) cerr << "[" << #a << "] = ", debug(a);

typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;

const int N = 2010;
const int INF = 0x3f3f3f3f;
const int base = 131;

template<typename Type>
inline void read(Type &res)
{
    res = 0;
    int ch = getchar(), flag = 0;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    res = flag ? -res : res;
}
template<typename Type, typename... Other>
inline void read(Type &res, Other&... y) { read(res), read(y...); }

int n, m, q;
char str[N][N];
ULL fc[N << 1], rhsh[N][N], dhsh[N][N], xhsh[N][N];

inline ULL gethash(int stx, int sty, int edx, int edy, int dir)
{
    if (dir == 0)
        return rhsh[edx][edy] - rhsh[stx][sty - 1] * fc[edy - sty + 1];
    if (dir == 1)
        return dhsh[edx][edy] - dhsh[stx - 1][sty] * fc[edx - stx + 1];
    else return xhsh[edx][edy] - xhsh[stx - 1][sty - 1] * fc[edy - sty + 1];
}

inline int getborder(int x, int y, int dir)
{
    if (dir == 0) return m - y + 1;
    if (dir == 1) return n - x + 1;
    if (dir == 2) return min(m - y + 1, n - x + 1);
}

inline bool check(int a, int b, int dir1, int x, int y, int dir2, int len)
{
    ULL res1 = 0, res2 = 0;
    if (dir1 == 0) res1 = gethash(a, b, a, b + len - 1, dir1);
    if (dir1 == 1) res1 = gethash(a, b, a + len - 1, b, dir1);
    if (dir1 == 2) res1 = gethash(a, b, a + len - 1, b + len - 1, dir1);

    if (dir2 == 0) res2 = gethash(x, y, x, y + len - 1, dir2);
    if (dir2 == 1) res2 = gethash(x, y, x + len - 1, y, dir2);
    if (dir2 == 2) res2 = gethash(x, y, x + len - 1, y + len - 1, dir2);

    return res1 == res2;
}

signed main()
{
    for (int i = fc[0] = 1; i < N << 1; i ++)
        fc[i] = fc[i - 1] * base;

    read(n, m, q);
    for (int i = 1; i <= n; i ++)
        scanf("%s", str[i] + 1);
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            rhsh[i][j] = rhsh[i][j - 1] * base + str[i][j];
    for (int j = 1; j <= m; j ++)
        for (int i = 1; i <= n; i ++)
            dhsh[i][j] = dhsh[i - 1][j] * base + str[i][j];
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            xhsh[i][j] = xhsh[i - 1][j - 1] * base + str[i][j];
    
    int a, b, x, y;
    char c[10], z[10];
    while (q --)
    {
        scanf("%lld%lld%s%lld%lld%s", &a, &b, c, &x, &y, z);
        int dir1 = *c == 'H' ? 0 : *c == 'V' ? 1 : 2, dir2 = *z == 'H' ? 0 : *z == 'V' ? 1 : 2;
        int l = 1, r = min(getborder(a, b, dir1), getborder(x, y, dir2)), res = 0;
        while (l <= r)
        {
            int mid = l + r >> 1;
            if (check(a, b, dir1, x, y, dir2, mid)) res = mid, l = mid + 1;
            else r = mid - 1;
        }
        cout << res << '\n';
    }

    return 0;
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 11
Accepted

Test #1:

score: 11
Accepted
time: 49ms
memory: 50336kb

input:

1000 2000 10000
awanannwnnaaawwnwawanwnwaaaanwnaaananwawwwwnannannawwwawwaaaaannwnwnwnnaaawaawawannn...

output:

0
0
0
0
0
0
0
2
0
1
0
0
1
0
1
0
2
0
1
2
0
0
2
0
1
1
0
0
0
0
1
0
0
0
1
0
0
1
0
1
1
0
2
0
1
3
1
0
3
0
...

result:

ok 10000 tokens

Test #2:

score: 0
Accepted
time: 50ms
memory: 76056kb

input:

2000 1000 10000
zzqzqqqqqzqqqqzqqqqzqzqzzzqqzqqqzzqzzqqqqqqqqqqqzzqzqqqzzqqzzqzqzzzqqzqqzzzzzzqzzzqq...

output:

0
3
3
1
0
2
2
2
1
0
1
0
0
0
1
0
2
0
6
1
0
1
1
0
2
1
1
1
2
4
0
1
3
2
1
0
1
2
0
0
0
1
1
0
1
1
0
4
0
3
...

result:

ok 10000 tokens

Subtask #2:

score: 24
Accepted

Test #3:

score: 24
Accepted
time: 721ms
memory: 99408kb

input:

2000 2000 1000000
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

1146
541
203
322
618
166
345
138
520
206
1031
667
741
921
361
1110
1057
372
899
209
491
69
93
639
14...

result:

ok 1000000 tokens

Test #4:

score: 0
Accepted
time: 803ms
memory: 99412kb

input:

2000 2000 1000000
svsvsvvsvssssvsvvvvssvvvssvsvsvssssvvsvvvsvvsssvssssvssvvsvvvssssssvsvvvvsssvvvsss...

output:

2
0
2
1
2
0
0
1
3
1
0
0
0
1
0
1
0
1
0
6
1
2
2
1
3
5
0
0
1
1
0
0
2
1
1
3
1
0
0
2
1
0
0
0
0
0
1
0
5
0
...

result:

ok 1000000 tokens

Test #5:

score: 0
Accepted
time: 891ms
memory: 99412kb

input:

2000 2000 1000000
qqqqqqqqqqqqqqqqcqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...

output:

327
50
54
421
87
4
189
135
200
214
55
578
82
72
335
52
45
110
521
267
123
21
293
105
105
479
85
69
1...

result:

ok 1000000 tokens

Test #6:

score: 0
Accepted
time: 1111ms
memory: 99412kb

input:

2000 2000 1000000
ssssssssssssssssssssssssssgsssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

187
336
26
367
487
65
159
30
12
275
628
200
252
742
362
7
316
232
26
82
607
158
56
444
155
262
1
106...

result:

ok 1000000 tokens

Test #7:

score: 0
Accepted
time: 1274ms
memory: 99408kb

input:

2000 2000 1000000
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...

output:

1281
105
890
1087
24
179
172
588
260
206
238
255
150
346
484
224
369
293
15
275
299
125
19
406
1146
...

result:

ok 1000000 tokens

Test #8:

score: 0
Accepted
time: 737ms
memory: 99408kb

input:

2000 2000 1000000
cschgfyhvrlhmuchmcssqmxypkfkmkrfwpivfljvlascqlphvlbmjnztypqeoyevqecixdhricknhdrero...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000000 tokens

Test #9:

score: 0
Accepted
time: 782ms
memory: 99408kb

input:

2000 2000 1000000
cwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcwcw...

output:

0
0
0
0
118
0
0
0
0
0
0
0
0
0
0
0
0
0
178
0
0
0
297
0
0
0
0
0
0
63
0
0
0
115
0
0
0
699
955
0
325
0
0...

result:

ok 1000000 tokens

Subtask #3:

score: 22
Accepted

Test #10:

score: 22
Accepted
time: 1420ms
memory: 99412kb

input:

2000 2000 1000000
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

1182
916
1440
420
469
1353
818
143
458
743
25
1414
878
23
284
453
324
1652
10
556
276
448
1143
916
1...

result:

ok 1000000 tokens

Test #11:

score: 0
Accepted
time: 1112ms
memory: 99412kb

input:

2000 2000 1000000
ddddoddoodoodooddodododdodododdoooddodddddoodoodddddoodddodooddoddooooodddooodddoo...

output:

4
1
1
1
2
0
0
0
4
2
1
1
3
0
0
0
1
4
1
1
0
0
0
2
1
2
1
0
2
0
2
0
2
0
4
4
1
1
0
0
2
0
5
2
0
1
2
1
0
0
...

result:

ok 1000000 tokens

Test #12:

score: 0
Accepted
time: 1715ms
memory: 99408kb

input:

2000 2000 1000000
dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd...

output:

180
74
19
380
126
169
75
17
53
352
123
150
258
103
65
17
87
109
11
164
407
143
241
407
214
256
84
22...

result:

ok 1000000 tokens

Test #13:

score: 0
Accepted
time: 1104ms
memory: 99408kb

input:

2000 2000 1000000
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

36
41
642
9
356
1100
529
595
2
299
253
559
761
245
494
259
43
234
430
885
449
225
404
211
213
32
38
...

result:

ok 1000000 tokens

Test #14:

score: 0
Accepted
time: 1049ms
memory: 99408kb

input:

2000 2000 1000000
dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd...

output:

905
292
231
537
281
229
247
240
1460
110
261
530
378
569
206
163
1185
128
983
117
296
79
123
3
53
81...

result:

ok 1000000 tokens

Test #15:

score: 0
Accepted
time: 1227ms
memory: 99412kb

input:

2000 2000 1000000
nvmqmtwqkbpisvkrhgehqvohvizhldbhyiamavjuipxwxeqcqiqwcrjjlxeuvgzpgfwtcdgpymkptfemtv...

output:

0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 1000000 tokens

Test #16:

score: 0
Accepted
time: 859ms
memory: 99408kb

input:

2000 2000 1000000
tctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctctc...

output:

0
0
0
0
0
0
0
0
0
0
1
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
344
0
0
0
0
0
0
0
0
0
0
0
1
0
0
546
0
0
0
1
1
...

result:

ok 1000000 tokens

Subtask #4:

score: 43
Accepted

Test #17:

score: 43
Accepted
time: 1332ms
memory: 50336kb

input:

1000 2000 1000000
yzyzzyaazyyzzaaayzzayyyaaayyazayyzzyazzyazayzayzyzzayyzyzzayzazzyzzayzaazazaaayzyy...

output:

2
0
2
1
1
0
1
0
0
1
0
1
0
0
0
1
1
0
0
0
0
1
0
0
0
1
1
0
0
0
1
0
2
0
1
0
0
0
0
2
1
2
0
1
0
0
0
2
0
0
...

result:

ok 1000000 tokens

Test #18:

score: 0
Accepted
time: 989ms
memory: 99408kb

input:

2000 2000 1000000
jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...

output:

255
79
826
62
931
351
68
1020
265
697
2
1101
779
606
176
1568
696
615
106
596
185
311
65
397
816
25
...

result:

ok 1000000 tokens

Test #19:

score: 0
Accepted
time: 1488ms
memory: 99412kb

input:

2000 2000 1000000
yyyvvyyyvyyyyvvvyyvyyyyvyyyyyyvvyvvyyyyyvvyyvvyvyvyvvvyyyvyvyvyyvyyyyvyyyvyyyvvyvy...

output:

3
0
0
0
0
1
0
0
0
0
1
2
0
2
1
0
0
0
4
2
0
0
3
1
1
2
3
1
0
1
1
0
0
3
0
0
0
2
0
0
1
0
1
0
0
3
2
0
0
1
...

result:

ok 1000000 tokens

Test #20:

score: 0
Accepted
time: 1448ms
memory: 99412kb

input:

2000 2000 1000000
jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...

output:

128
57
641
99
820
2
155
264
232
511
552
36
506
522
31
528
574
506
638
59
127
22
103
53
30
56
14
18
1...

result:

ok 1000000 tokens

Test #21:

score: 0
Accepted
time: 1559ms
memory: 99412kb

input:

2000 2000 1000000
ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

1
33
165
12
417
104
452
86
315
401
295
141
60
41
76
115
118
150
489
69
46
196
373
109
142
34
115
481...

result:

ok 1000000 tokens

Test #22:

score: 0
Accepted
time: 1073ms
memory: 99412kb

input:

2000 2000 1000000
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

371
247
218
9
492
569
21
454
121
168
207
251
176
236
333
23
138
1501
385
306
342
101
286
204
168
99
...

result:

ok 1000000 tokens

Test #23:

score: 0
Accepted
time: 901ms
memory: 99412kb

input:

2000 2000 1000000
ccbxyakkmwxjxctespteblasatcayufpdpqvjjbmatywntdpcnhmwabgpmsyuxvqjtgxutglopldstpcmq...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
...

result:

ok 1000000 tokens

Test #24:

score: 0
Accepted
time: 1354ms
memory: 99408kb

input:

2000 2000 1000000
mfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmfmf...

output:

0
0
0
0
2
0
0
1
0
1
0
0
0
0
0
0
2
1
0
361
0
0
0
1
0
0
0
0
1
1
0
1
0
0
1
0
0
0
0
0
323
0
0
0
1
0
0
1
...

result:

ok 1000000 tokens