QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#686315#5414. Stop, Yesterday Please No Moreucup-team3474AC ✓90ms28248kbC++202.3kb2024-10-29 11:09:062024-10-29 11:09:07

Judging History

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

  • [2024-10-29 11:09:07]
  • 评测
  • 测评结果:AC
  • 用时:90ms
  • 内存:28248kb
  • [2024-10-29 11:09:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;
int n,m,k;
int a[N],b[N];
char s[N];
ll c[2010][2010];

void add(int x,int y,int lenx,int leny){
    int xx=x+lenx-1,yy=y+leny-1;
    x=max(1,x),y=max(1,y);
    xx=min(n,xx),yy=min(m,yy);
    if(xx<=0||yy<=0) return;
    c[x][y]++;
    c[xx+1][yy+1]++;
    c[xx+1][y]--;
    c[x][yy+1]--;
}

void __(){
    cin>>n>>m>>k;
    int l=1,r=m,u=1,d=n;
    scanf("%s",s+1);
    int dx=0,dy=0;
    int len=strlen(s+1);
    for(int i=1;i<=len;i++){
        if(s[i]=='U') u++;
        else if(s[i]=='D') d--;
        else if(s[i]=='L') l++;
        else r--;
    }
    int leny=r-l+1,lenx=d-u+1;
    
    int mn=0,mx=0,res=0;
    for(int i=1;i<=len;i++){
        if(s[i]=='U') res--;
        else if(s[i]=='D') res++;
        mn=min(mn,res),mx=max(mx,res);
    }
    dx=1-mn;
    // cout<<mn<<" "<<mx<<endl;
    lenx=max(n-(mx-mn),0);
    mn=0,mx=0,res=0;
    for(int i=1;i<=len;i++){
        if(s[i]=='L') res--;
        else if(s[i]=='R') res++;
        mn=min(mn,res),mx=max(mx,res);
    }
    dy=1-mn;
    // cout<<mn<<" "<<mx<<endl;
    leny=max(m-(mx-mn),0);
    ll tot=lenx*leny;
    // cout<<lenx<<" "<<leny<<endl;
    if(tot==0){
        if(k==0) printf("%d\n",n*m);
        else puts("0");
        return;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) c[i][j]=0;
    }
    // dx=u,dy=l;
    // cout<<tot<<" "<<dx<<" "<<dy<<endl;
    // int rx=u,ry=l;
    set<PII> se;
    se.insert({dx,dy});
    // add(dx,dy,lenx,leny);
    for(int i=1;i<=len;i++){
        if(s[i]=='D') dx++;
        else if(s[i]=='U') dx--;
        else if(s[i]=='R') dy++;
        else dy--;
        se.insert({dx,dy});
        // add(dx,dy,lenx,leny);
    }
    for(auto [u,v]:se) add(u,v,lenx,leny);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            c[i][j]+=(c[i-1][j]+c[i][j-1]-c[i-1][j-1]);
        }
    }
    int ans=0;
    // cout<<tot<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            // cout<<c[i][j]<<" ";
            if(tot-c[i][j]==k) ans++;
        }
        // cout<<endl;
    }
    printf("%d\n",ans);
}


int main(){
    int _=1;
    cin>>_;
    while(_--){
        __();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5860kb

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: 8ms
memory: 8444kb

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: 0ms
memory: 22572kb

input:

1
1000 1000 979065
DDUULULUDULLULLDLUULURRLDURLRDLRRUURUUUDLRLUUDUUDUDLLDDDULU

output:

958416

result:

ok 1 number(s): "958416"

Test #4:

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

input:

1
1000 1000 943471
LRLDLURLDLRDRDUULULRDDLLRURDUURLLDDLDLDDLLLUUURLDRUDRLLUUUUUDLUUDLURURRDLRLRRRLULRRULURLRRDLDRLUDRRLDDLUDRRLLUDLLLRDULRRRRLDUUDRDLULUUUUDRRDULUDLLUUDLDURDRRLRRLDRLDDRURURLUULRRLDLLRLRDRRUULDLDLULLDLLRULLRUULURDURRLUUDUULLULDLRUDDLRLRLLUDDDLLLUDRRLDDULRRURRDURDDRDLLULRLULURLRDLLURD...

output:

889224

result:

ok 1 number(s): "889224"

Test #5:

score: 0
Accepted
time: 90ms
memory: 28248kb

input:

1
1000 1000 315808
LLRURURRDDDULLDDUDRDLRLLLDDDLUDRDURLDULRLRULUUDLUULUUDULLLLDDURLDUULUUDLLDLLDRUDUULRLLRLRUURLRLULLDDLLDUDLLRUUDRLDLUULDLLDRRRURDULLDRRRDURURDRLDURURUDLURLDURRLRRUDUDURDRLRRRDLRRURLURUDRRLDLRULLDLUURDURLURLLRDLRDRUURURDRUDUUUDLRRLUDLUUDUDDRRDUULUUDDRLLULDUUDRURRDRLULRLULDURLURUDLLD...

output:

426

result:

ok 1 number(s): "426"

Test #6:

score: 0
Accepted
time: 0ms
memory: 22376kb

input:

1
1000 1000 986018
LLULDRRRDDURRUDRUURRRDDLUUDUULRULRDULLD

output:

972180

result:

ok 1 number(s): "972180"

Test #7:

score: 0
Accepted
time: 7ms
memory: 21720kb

input:

1
1000 1000 945431
DDRRURUUDLDULLDLDDLRULDLLDDRRLUDRLUURRLDRDLURUURRRRLRURLURULLLDRDDDRRRLDLDRLRDDUURRURDDDLRUURLUURLRDUDDDLLDUURLDLUDLLRRDUUDRLUULLUULDLURRUDLUURLRLRURDUDRRRDRLRUDLLLLURLULRLRLRRDDUDLRLDUUUULUDLLURRLURRDLRURRRULDDLLLRLRDLUDLLDDRULDUULRDDUUDDUDLURDULLDUDDLULRULDRLDDULDULLUDLULUDRURRR...

output:

893000

result:

ok 1 number(s): "893000"

Test #8:

score: 0
Accepted
time: 80ms
memory: 25268kb

input:

1
1000 1000 460035
RDDUURDULDDLDDLDDLDRRULLRLUURLURRRDRUDDDRDLDLDULUDLRLLRRLRRURRRDLRLUDRDURULDRRDDDDDDLRLDULUULDUDRLLUUUURUUDRURLRRULDRDRUUUUULULRURDDRLRULLLRDRRULUDDUDDLLLRDRUULUUDDRLURDLDURRDLRRLDRRUDLUULRDLURULLDLRLLDDURDUDLDULDLLRULRDLRLUULLUDRUDDDLRRDULULLRUURLUURRLLLLRLDRURLLRLDRRDDDRLUUUUDUL...

output:

417

result:

ok 1 number(s): "417"

Test #9:

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

input:

1
1000 1000 992010
LLLLLDLDRRLUDRR

output:

1999

result:

ok 1 number(s): "1999"

Test #10:

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

input:

1
1000 1000 919600
LLDLRUDRLURRUDRDRRDLRUDLRRRUUULDLDURDDDRUURRRLLURULDRLRLULLULDRULULRLRRRURLDDDRUUULUDLLLLRRLLRDDRDULUDLRLRLDRLUDUDURRULUULLDULUULDLLDRDULUDLDULDDUULDDRRURDRDULRRLDRRDUURURRLUUUDRRLDRRDDLULRDDLDLLRLRLLLRULUUUURRRLDLRUDRRLRURDRLDULLLUDRULLDLDRRUUDLRRLLRLDDLUDLRLRRURUUDUULUDURDURRLUU...

output:

944

result:

ok 1 number(s): "944"

Test #11:

score: 0
Accepted
time: 70ms
memory: 23060kb

input:

1
1000 1000 804351
DLRLDLLLLUDRDURRLDDRRLRUULURURDDDRDLRUDDULRRLLULURDRUUDRURRLURRRDRURRDRLULRDLRRDRRDDUDLUDLDULRUURRLRUUDRLDDRDDUUDULUULUUUDLRURULLRDUUDDDRRLDRUDDUUDRURLRDRUDLRLDDRRLLRLRDUDDULLULRLLDDUDDDUULDULLRRULULDUUULUDRRDRLUDLRRDDUDLRRDDLDLDRUULRRRRRLRLULLRDDRDDDULDRRURUDDLURLRLURLRDRULUDULUU...

output:

640000

result:

ok 1 number(s): "640000"