QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#879878#5414. Stop, Yesterday Please No MoreThe_8th_HorcruxAC ✓213ms9440kbC++231.8kb2025-02-02 17:05:382025-02-02 17:05:39

Judging History

This is the latest submission verdict.

  • [2025-02-02 17:05:39]
  • Judged
  • Verdict: AC
  • Time: 213ms
  • Memory: 9440kb
  • [2025-02-02 17:05:38]
  • Submitted

answer

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

#define endl '\n'

const int N = 1010;

string op;

int n, m, k;
int U, D, L, R, U_, D_, L_, R_;
bool st[N][N];
int g[N][N];

void add(int x1, int y1, int x2, int y2){
    if (st[x1][y1])
        return;
    st[x1][y1] = true;
    g[x1][y1]++, g[x2 + 1][y1]--, g[x1][y2 + 1]--, g[x2 + 1][y2 + 1]++;
}

void solve(){
    cin >> n >> m >> k >> op;
    U_ = L_ = U = L = 1, R_ = R = m, D_ = D = n;
    memset(st, false, sizeof st), memset(g, 0, sizeof g);
    //确定边界
    for (auto i: op){
        if (i == 'L')
            L_++, R_++;
        else if (i == 'R')
            L_--, R_--;
        else if (i == 'U')
            U_++, D_++;
        else
            U_--, D_--;
        L = max(L, L_), R = min(R, R_), U = max(U, U_), D = min(D, D_);
    }
    //无袋鼠剩余情况
    if (U > D || L > R){
        if (k)
            puts("0");
        else
            cout << n * m << endl;
        return;
    }
    //统计袋鼠经过格子的情况
    int x = (D - U + 1) * (R - L + 1), cnt = 0;
    add(U, L, D, R);
    for (auto i: op){
        if (i == 'L')
            L--, R--;
        else if (i == 'R')
            L++, R++;
        else if (i == 'U')
            U--, D--;
        else
            U++, D++;
        add(U, L, D, R);
    }
    //二位前缀和+统计答案
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            if (x - g[i][j] == k)
                 cnt++;
    cout << cnt << endl;
}

int main(){
    int _;
    cin >> _;
    while (_ -- )
        solve();
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 8568kb

input:

3
4 5 3
ULDDRR
4 5 0
UUUUUUU
4 5 10
UUUUUUU

output:

2
20
0

result:

ok 3 number(s): "2 20 0"

Test #2:

score: 0
Accepted
time: 213ms
memory: 8640kb

input:

1060
19 12 0
UDLDDUUUUDDDLLRDUDUURULUUUDRDUDRDRLRLRLULULLLDLDDRLUUUURUUUDDRLLRUUUDULURUULLRDRLRDDURDUUURRRLURLRUULRRUDURDLUUURDLURDDLUUURDDRLLURRDLRUDLRDRLLRRDRDDLDRURRRLUDULLLRUUDLRRURRDLLRRRDLLRDDDLRLRURURDDDL
11 1 0
UR
3 18 33
UDRLR
17 11 132
RLDRDLDRUU
6 10 13
UULUDDLRDLUUDLDD
1 15 0
D
6 20 50
D...

output:

228
11
20
99
18
15
34
240
15
0
0
13
14
18
26
16
1
19
108
8
2
2
3
7
0
30
16
21
0
8
10
9
15
5
320
11
7
3
0
0
12
0
11
0
0
14
0
22
36
51
23
7
6
4
2
48
28
8
63
22
49
13
10
4
108
10
18
44
0
15
9
0
4
30
14
99
105
10
14
17
0
66
10
11
28
52
34
56
33
14
56
90
14
0
121
3
48
30
36
13
0
30
7
8
3
11
16
45
20
34
0...

result:

ok 1060 numbers

Test #3:

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

input:

1
1000 1000 979065
DDUULULUDULLULLDLUULURRLDURLRDLRRUURUUUDLRLUUDUUDUDLLDDDULU

output:

958416

result:

ok 1 number(s): "958416"

Test #4:

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

input:

1
1000 1000 943471
LRLDLURLDLRDRDUULULRDDLLRURDUURLLDDLDLDDLLLUUURLDRUDRLLUUUUUDLUUDLURURRDLRLRRRLULRRULURLRRDLDRLUDRRLDDLUDRRLLUDLLLRDULRRRRLDUUDRDLULUUUUDRRDULUDLLUUDLDURDRRLRRLDRLDDRURURLUULRRLDLLRLRDRRUULDLDLULLDLLRULLRUULURDURRLUUDUULLULDLRUDDLRLRLLUDDDLLLUDRRLDDULRRURRDURDDRDLLULRLULURLRDLLURD...

output:

889224

result:

ok 1 number(s): "889224"

Test #5:

score: 0
Accepted
time: 30ms
memory: 9428kb

input:

1
1000 1000 315808
LLRURURRDDDULLDDUDRDLRLLLDDDLUDRDURLDULRLRULUUDLUULUUDULLLLDDURLDUULUUDLLDLLDRUDUULRLLRLRUURLRLULLDDLLDUDLLRUUDRLDLUULDLLDRRRURDULLDRRRDURURDRLDURURUDLURLDURRLRRUDUDURDRLRRRDLRRURLURUDRRLDLRULLDLUURDURLURLLRDLRDRUURURDRUDUUUDLRRLUDLUUDUDDRRDUULUUDDRLLULDUUDRURRDRLULRLULDURLURUDLLD...

output:

426

result:

ok 1 number(s): "426"

Test #6:

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

input:

1
1000 1000 986018
LLULDRRRDDURRUDRUURRRDDLUUDUULRULRDULLD

output:

972180

result:

ok 1 number(s): "972180"

Test #7:

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

input:

1
1000 1000 945431
DDRRURUUDLDULLDLDDLRULDLLDDRRLUDRLUURRLDRDLURUURRRRLRURLURULLLDRDDDRRRLDLDRLRDDUURRURDDDLRUURLUURLRDUDDDLLDUURLDLUDLLRRDUUDRLUULLUULDLURRUDLUURLRLRURDUDRRRDRLRUDLLLLURLULRLRLRRDDUDLRLDUUUULUDLLURRLURRDLRURRRULDDLLLRLRDLUDLLDDRULDUULRDDUUDDUDLURDULLDUDDLULRULDRLDDULDULLUDLULUDRURRR...

output:

893000

result:

ok 1 number(s): "893000"

Test #8:

score: 0
Accepted
time: 29ms
memory: 9328kb

input:

1
1000 1000 460035
RDDUURDULDDLDDLDDLDRRULLRLUURLURRRDRUDDDRDLDLDULUDLRLLRRLRRURRRDLRLUDRDURULDRRDDDDDDLRLDULUULDUDRLLUUUURUUDRURLRRULDRDRUUUUULULRURDDRLRULLLRDRRULUDDUDDLLLRDRUULUUDDRLURDLDURRDLRRLDRRUDLUULRDLURULLDLRLLDDURDUDLDULDLLRULRDLRLUULLUDRUDDDLRRDULULLRUURLUURRLLLLRLDRURLLRLDRRDDDRLUUUUDUL...

output:

417

result:

ok 1 number(s): "417"

Test #9:

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

input:

1
1000 1000 992010
LLLLLDLDRRLUDRR

output:

1999

result:

ok 1 number(s): "1999"

Test #10:

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

input:

1
1000 1000 919600
LLDLRUDRLURRUDRDRRDLRUDLRRRUUULDLDURDDDRUURRRLLURULDRLRLULLULDRULULRLRRRURLDDDRUUULUDLLLLRRLLRDDRDULUDLRLRLDRLUDUDURRULUULLDULUULDLLDRDULUDLDULDDUULDDRRURDRDULRRLDRRDUURURRLUUUDRRLDRRDDLULRDDLDLLRLRLLLRULUUUURRRLDLRUDRRLRURDRLDULLLUDRULLDLDRRUUDLRRLLRLDDLUDLRLRRURUUDUULUDURDURRLUU...

output:

944

result:

ok 1 number(s): "944"

Test #11:

score: 0
Accepted
time: 29ms
memory: 9440kb

input:

1
1000 1000 804351
DLRLDLLLLUDRDURRLDDRRLRUULURURDDDRDLRUDDULRRLLULURDRUUDRURRLURRRDRURRDRLULRDLRRDRRDDUDLUDLDULRUURRLRUUDRLDDRDDUUDULUULUUUDLRURULLRDUUDDDRRLDRUDDUUDRURLRDRUDLRLDDRRLLRLRDUDDULLULRLLDDUDDDUULDULLRRULULDUUULUDRRDRLUDLRRDDUDLRRDDLDLDRUULRRRRRLRLULLRDDRDDDULDRRURUDDLURLRLURLRDRULUDULUU...

output:

640000

result:

ok 1 number(s): "640000"