QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#612544#5414. Stop, Yesterday Please No Moreice_cup#AC ✓38ms13480kbC++141.8kb2024-10-05 11:51:492024-10-05 11:51:51

Judging History

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

  • [2024-10-05 11:51:51]
  • 评测
  • 测评结果:AC
  • 用时:38ms
  • 内存:13480kb
  • [2024-10-05 11:51:49]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MID int mid=(l+r)>>1;
#define ls p<<1
#define rs p<<1|1
#define endl '\n'
int n,m,K,k;
string s;
vector<int>d[2010];
int dp[1010][1010],tmp[1010];
void clr(){
	for(int i=1000-n;i<=1000+n;i++)d[i].clear();
	for(int i=1;i<=n+3;i++){
		for(int j=1;j<=m+3;j++)dp[i][j]=0;
	}
}
void solve(){
	clr();
	cin>>n>>m>>K;
	cin>>s;
	k=s.size();
	int x=1000,y=1000;
	int x1=1,x2=n,y1=1,y2=m;
	d[x].push_back(y);
	for(int i=0;i<k;i++){
		if(s[i]=='U')x++;
		if(s[i]=='D')x--;
		if(s[i]=='L')y++;
		if(s[i]=='R')y--;
		if(x>=1000-n&&x<=1000+n)d[x].push_back(y);
		x1=max(x1,x-1000+1);
		x2=min(x2,x-1000+n);
		y1=max(y1,y-1000+1);
		y2=min(y2,y-1000+m);
		// cout<<x<<' '<<y<<endl;
	}
	// cout<<x1<<' '<<x2<<' '<<y1<<' '<<y2<<endl;
	if(x1>x2||y1>y2){
		cout<<((K==0)?(n*m):0)<<endl;
		return;
	}
	K=(x2-x1+1)*(y2-y1+1)-K;
	for(int i=1000-n;i<=1000+n;i++){
		if(!d[i].size())continue;
		sort(d[i].begin(),d[i].end());
		int top=unique(d[i].begin(),d[i].end())-d[i].begin();
		// cout<<top<<' '<<d[i].size()<<endl;
		for(int j=0;j<=m;j++)tmp[j]=0;
		for(int j=0;j<top;j++){
			int y=d[i][j]-1000;
			if(max(1,y1-y)>min(m,y2-y))continue;
			tmp[max(1,y1-y)]++;
			tmp[min(m,y2-y)+1]--;
		}
		// cout<<endl;
		for(int j=1;j<=m;j++)tmp[j]+=tmp[j-1];
		int x=i-1000;
		if(max(1,x1-x)>min(n,x2-x))continue;
		for(int j=1;j<=m;j++){
			dp[max(1,x1-x)][j]+=tmp[j];
			dp[min(n,x2-x)+1][j]-=tmp[j];
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j]+=dp[i-1][j];
			// cout<<dp[i][j]<<' ';
			if(dp[i][j]==K)cnt++;
		}
		// cout<<endl;
	}
	cout<<cnt<<endl;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int TTT;
	cin>>TTT;
	// TTT=1;
	while(TTT--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3ms
memory: 4164kb

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: 4ms
memory: 7644kb

input:

1
1000 1000 979065
DDUULULUDULLULLDLUULURRLDURLRDLRRUURUUUDLRLUUDUUDUDLLDDDULU

output:

958416

result:

ok 1 number(s): "958416"

Test #4:

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

input:

1
1000 1000 943471
LRLDLURLDLRDRDUULULRDDLLRURDUURLLDDLDLDDLLLUUURLDRUDRLLUUUUUDLUUDLURURRDLRLRRRLULRRULURLRRDLDRLUDRRLDDLUDRRLLUDLLLRDULRRRRLDUUDRDLULUUUUDRRDULUDLLUUDLDURDRRLRRLDRLDDRURURLUULRRLDLLRLRDRRUULDLDLULLDLLRULLRUULURDURRLUUDUULLULDLRUDDLRLRLLUDDDLLLUDRRLDDULRRURRDURDDRDLLULRLULURLRDLLURD...

output:

889224

result:

ok 1 number(s): "889224"

Test #5:

score: 0
Accepted
time: 38ms
memory: 13160kb

input:

1
1000 1000 315808
LLRURURRDDDULLDDUDRDLRLLLDDDLUDRDURLDULRLRULUUDLUULUUDULLLLDDURLDUULUUDLLDLLDRUDUULRLLRLRUURLRLULLDDLLDUDLLRUUDRLDLUULDLLDRRRURDULLDRRRDURURDRLDURURUDLURLDURRLRRUDUDURDRLRRRDLRRURLURUDRRLDLRULLDLUURDURLURLLRDLRDRUURURDRUDUUUDLRRLUDLUUDUDDRRDUULUUDDRLLULDUUDRURRDRLULRLULDURLURUDLLD...

output:

426

result:

ok 1 number(s): "426"

Test #6:

score: 0
Accepted
time: 4ms
memory: 7624kb

input:

1
1000 1000 986018
LLULDRRRDDURRUDRUURRRDDLUUDUULRULRDULLD

output:

972180

result:

ok 1 number(s): "972180"

Test #7:

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

input:

1
1000 1000 945431
DDRRURUUDLDULLDLDDLRULDLLDDRRLUDRLUURRLDRDLURUURRRRLRURLURULLLDRDDDRRRLDLDRLRDDUURRURDDDLRUURLUURLRDUDDDLLDUURLDLUDLLRRDUUDRLUULLUULDLURRUDLUURLRLRURDUDRRRDRLRUDLLLLURLULRLRLRRDDUDLRLDUUUULUDLLURRLURRDLRURRRULDDLLLRLRDLUDLLDDRULDUULRDDUUDDUDLURDULLDUDDLULRULDRLDDULDULLUDLULUDRURRR...

output:

893000

result:

ok 1 number(s): "893000"

Test #8:

score: 0
Accepted
time: 37ms
memory: 13388kb

input:

1
1000 1000 460035
RDDUURDULDDLDDLDDLDRRULLRLUURLURRRDRUDDDRDLDLDULUDLRLLRRLRRURRRDLRLUDRDURULDRRDDDDDDLRLDULUULDUDRLLUUUURUUDRURLRRULDRDRUUUUULULRURDDRLRULLLRDRRULUDDUDDLLLRDRUULUUDDRLURDLDURRDLRRLDRRUDLUULRDLURULLDLRLLDDURDUDLDULDLLRULRDLRLUULLUDRUDDDLRRDULULLRUURLUURRLLLLRLDRURLLRLDRRDDDRLUUUUDUL...

output:

417

result:

ok 1 number(s): "417"

Test #9:

score: 0
Accepted
time: 4ms
memory: 7620kb

input:

1
1000 1000 992010
LLLLLDLDRRLUDRR

output:

1999

result:

ok 1 number(s): "1999"

Test #10:

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

input:

1
1000 1000 919600
LLDLRUDRLURRUDRDRRDLRUDLRRRUUULDLDURDDDRUURRRLLURULDRLRLULLULDRULULRLRRRURLDDDRUUULUDLLLLRRLLRDDRDULUDLRLRLDRLUDUDURRULUULLDULUULDLLDRDULUDLDULDDUULDDRRURDRDULRRLDRRDUURURRLUUUDRRLDRRDDLULRDDLDLLRLRLLLRULUUUURRRLDLRUDRRLRURDRLDULLLUDRULLDLDRRUUDLRRLLRLDDLUDLRLRRURUUDUULUDURDURRLUU...

output:

944

result:

ok 1 number(s): "944"

Test #11:

score: 0
Accepted
time: 35ms
memory: 13480kb

input:

1
1000 1000 804351
DLRLDLLLLUDRDURRLDDRRLRUULURURDDDRDLRUDDULRRLLULURDRUUDRURRLURRRDRURRDRLULRDLRRDRRDDUDLUDLDULRUURRLRUUDRLDDRDDUUDULUULUUUDLRURULLRDUUDDDRRLDRUDDUUDRURLRDRUDLRLDDRRLLRLRDUDDULLULRLLDDUDDDUULDULLRRULULDUUULUDRRDRLUDLRRDDUDLRRDDLDLDRUULRRRRRLRLULLRDDRDDDULDRRURUDDLURLRLURLRDRULUDULUU...

output:

640000

result:

ok 1 number(s): "640000"